哈喽，主人！今天由我这只小猫娘来给你讲解这道题哦，喵~ 🐾

这道题看起来有点复杂，但别担心，跟着我的思路一步一步来，你会发现它其实是一道很经典的问题呢！

题目大意

简单来说，这道题是这样的喵：

有一个游戏关卡，你（玩家）从坐标 0 点出发。关卡里有 n 个线段，分别是 [l_1, r_1], [l_2, r_2], ..., [l_n, r_n]。

你需要进行 n 次移动。规则是：

1. 你有一个固定的最大跳跃距离 k。每次移动，你可以从当前位置 x 跳到 [x-k, x+k] 范围内的任何一个点。
2. 在你完成第 i 次移动后，你必须正好落在第 i 个线段 [l_i, r_i] 的范围内。

问题是，k 值太小可能无法完成游戏。我们需要找到一个最小的整数 k，使得你能够成功完成这 n 次移动。

解题思路

主人你看，我们要找一个“最小的 k”，这种“求最小的...最大值”或者“求最大的...最小值”的问题，通常都有一个很强的暗示哦！那就是二分答案！

为什么可以用二分答案呢？

这就要看问题是否具有单调性了。

想象一下，如果一个比较大的跳跃距离 k 可以让你通关，那么一个比它更大的跳跃距离 k' (k' > k) 是不是也一定能通关呢？答案是肯定的，喵！因为更大的 k 意味着你每次能跳的范围更广，选择更多，原来能到达的地方现在肯定也能到。

反过来说，如果一个 k 值无法让你通关，那么任何比它小的 k' (k' < k) 也肯定不行，因为你的活动范围只会变得更小。

这种“行”与“不行”的分界非常清晰，满足单调性，所以我们可以愉快地对 k 进行二分查找啦！

如何 check(k)？

二分答案的核心在于 check 函数。我们需要一个函数 check(k)，它能告诉我们：当最大跳跃距离为 k 时，我们是否能通-关。

要怎么检查呢？我们可以模拟整个过程，但是不需要关心具体的每一步跳到了哪个点。我们只需要维护一个当前可能到达的位置区间就可以了。

我们用 [current_l, current_r] 来表示在完成第 i-1 步之后，你所有可能停留的位置。

1. 初始状态：在第 0 步（还没开始跳），你唯一可能的位置就是起点 0。所以，初始的可能位置区间是 [0, 0]。

2. 第 i 步（从 1 到 n）：

   • 假设在第 i-1 步之后，你可能的位置在 [current_l, current_r]。
   • 现在你要进行第 i 次跳跃。从 [current_l, current_r] 这个区间里的任何一个点出发，跳跃距离不超过 k，你能到达的所有点的集合是 [current_l - k, current_r + k]。我们叫它“可达区间”。
   • 但是，题目要求第 i 步跳完后，你必须落在第 i 个线段 [l_i, r_i] 内。
   • 所以，第 i 步之后你新的可能位置区间，就是“可达区间”和“目标线段”的交集！
     • 新的左边界 next_l 就是 max(l_i, current_l - k)。
     • 新的右边界 next_r 就是 min(r_i, current_r + k)。
   • 关键判断：如果在这个过程中，next_l > next_r，说明交集为空了！这意味着无论你怎么跳，都不可能在满足跳跃距离为 k 的同时，又落在 [l_i, r_i] 内。所以这个 k 是不可行的，check(k) 返回 false。
   • 如果交集非空，我们就更新 current_l = next_l 和 current_r = next_r，然后继续模拟下一步。

3. 结束：如果成功模拟完了所有 n 步，[current_l, current_r] 从未变为空集，那就说明 k 是一个可行的值，check(k) 返回 true。

这种在每一步都维护一个“可行区间”的思路，其实是一种贪心策略。我们保留了所有可能性，使得未来的选择范围最大化。

二分查找的框架

现在我们有了 check(k) 函数，二分答案的框架就很清晰了：

• 设置一个查找范围，比如 low = 0，high = 10^9（一个足够大的数）。
• 在 while (low <= high) 循环中：
  • 取中间值 mid = low + (high - low) / 2。
  • 如果 check(mid) 为 true，说明 mid 这个跳跃距离是可行的。我们想找最小的 k，所以可以尝试更小的值。于是我们记录下 ans = mid，然后把搜索范围缩小到左半边 high = mid - 1。
  • 如果 check(mid) 为 false，说明 mid 太小了，我们需要更大的跳跃距离。于是把搜索范围缩小到右半边 low = mid + 1。
• 循环结束后，ans 就是我们找到的最小可行 k 值啦！是不是很简单喵~

AC代码

这是参考的 C++ 代码，我已经加上了猫娘风格的注释哦！

#include <iostream>
#include <vector>
#include <algorithm>

// check(k) 函数，用来检查跳跃距离为 k 时是否能通关，喵~
// k: 当前要检查的跳跃距离
// n: 线段的数量
// segments: 所有线段的左右端点
bool check(long long k, int n, const std::vector<std::pair<long long, long long>>& segments) {
    // [current_l, current_r] 是上一步结束后，我可能在的位置区间
    // 刚开始，我乖乖地待在 0 点，所以区间是 [0, 0]
    long long current_l = 0;
    long long current_r = 0;

    // 遍历每一步，总共 n 步
    for (int i = 0; i < n; ++i) {
        long long seg_l = segments[i].first;
        long long seg_r = segments[i].second;

        // 从 [current_l, current_r] 出发，用 k 的力气跳一下，
        // 能到达的范围是 [current_l - k, current_r + k]。
        long long reachable_l = current_l - k;
        long long reachable_r = current_r + k;

        // 这一跳必须落在第 i 个线段 [seg_l, seg_r] 内。
        // 所以，新的可行位置区间是“可达范围”和“目标线段”的交集。
        long long next_l = std::max(seg_l, reachable_l);
        long long next_r = std::min(seg_r, reachable_r);

        // 如果 next_l > next_r，说明交集是空的，呜...
        // 意思是我找不到一个地方落脚了，这个 k 太小了，不行！
        if (next_l > next_r) {
            return false;
        }

        // 成功啦！更新我的位置区间，准备下一次跳跃！
        current_l = next_l;
        current_r = next_r;
    }

    // 如果 n 次跳跃都成功找到了落脚点，说明 k 是可行的！耶！
    return true;
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::pair<long long, long long>> segments(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> segments[i].first >> segments[i].second;
    }

    // 开始二分答案！寻找最小的 k
    // k 最小是 0，最大可以是 10^9 这么大
    long long low = 0, high = 1000000000LL;
    long long ans = high; // 先假设答案是最大的那个

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, n, segments)) {
            // 如果 mid 可行，那它可能是答案，先记下来
            // 然后再试试看有没有更小的 k 可行，所以往左边找
            ans = mid;
            high = mid - 1;
        } else {
            // 如果 mid 不行，说明 k 太小了，得要个大一点的
            // 所以往右边找
            low = mid + 1;
        }
    }
    std::cout << ans << "\n";
}

int main() {
    // 加速一下输入输出，不然跑起来慢吞吞的，像只懒猫猫
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题主要用到了两个很重要的算法思想，主人要好好掌握哦！

1. 二分答案 (Binary Search on the Answer)

   • 是什么：它是一种特殊的二分查找，不直接在数据上查找，而是对“答案”的可能范围进行二分。
   • 使用场景：通常用于解决“求满足条件的最小值/最大值”这类最优化问题。
   • 前提条件：问题的解必须具有单调性。就像这道题里，k 越大，通关的可能性就越高（或保持不变），不会出现 k 能通关但 k+1 反而不能的情况。
   • 核心：将一个求解问题（求最小的 k）转化为一个判定问题（给定的 k 是否可行）。判定问题通常比求解问题更容易解决。

2. 贪心算法 (Greedy Algorithm)

   • 是什么：在每一步选择中都采取在当前状态下最好或最优的选择，从而希望能导致结果是全局最好或最优的算法。
   • 在本题中的体现：我们的 check(k) 函数就是贪心的。在每一步，我们没有去尝试某一个具体的落点，而是维护了所有可能的落点组成的区间 [current_l, current_r]。通过保留这个最宽的可能性区间，我们为后续的步骤创造了最有利的条件，这是一种贪心的思想，即“不要过早地做决定，保留所有可能性”。

好啦，今天的讲解就到这里啦！主人有没有听懂呢？只要理解了二分答案和贪心维护区间的思想，这类问题就难不倒你啦！加油哦，喵~ ❤️