今天来分享一道洛谷上的P2678 [NOIP 2015 提高组] 跳石头，很好的体现了二分的概念。先贴一下代码。

#include <bits/stdc++.h>
using namespace std;

bool isPossible(long long a[], int N, int M, long long mid) {
    int count = 0;
    long long last = 0;
    for (int i = 1; i <= N + 1; ++i) {
        if (a[i] - last < mid) {
            count++;  // 需要移除这块岩石
        } else {
            last = a[i];  // 保留这块岩石
        }
    }
    return count <= M;  // 移除的岩石数不超过 M
}

int main() {
    long long L;
    int N, M;
    long long a[50002];
    cin >> L >> N >> M;
    a[0] = 0;
    a[N + 1] = L;
    for (int i = 1; i <= N; ++i) {
        cin >> a[i];
    }

    long long left = 1, right = L;
    long long answer = 0;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (isPossible(a, N, M, mid)) {
            answer = mid;  // 当前 mid 可行，尝试更大的
            left = mid + 1;
        } else {
            right = mid - 1;  // 当前 mid 不可行，尝试更小的
        }
    }
    cout << answer << endl;
    return 0;
}

博主一开始想用贪心的方法去做，但后来发现贪心终究只能实现局部最优，而在本题局部最优不一定是全局最优。而且要选择移出哪几块石头使得全局石头之间的最短距离最长，这样就显得非常困难。而换另一个思路，可以从答案入手，我先枚举距离，看看移出不超过所能移出的最大石头数量，能不能让最短距离大于我所选择的距离，如果移出的石头数量超过了，那就是不行。而通过枚举，效率有点太低了，这时候就可以使用二分。首先来说说什么时候能用二分法，需要满足两个条件。一个是有界，一个是单调。题目里的最短距离显然在0和最大距离之间，石头也是从小到大排的，也是有序的。那么就可以使用二分法来判断，因为如果这个距离符合，那么比他小的肯定符合，只要找还有没有可能比他更大。这里再贴一个二分法的非递归模版。

while (l < r) {
    mid = (l + r + 1) / 2;
    if (check(mid)) l = mid;
    else r = mid - 1;
}

那么对于本题就可以写一个判断函数，来计算有多少个石头之间的距离可能比最短距离小，然后把他们移除，每次移除后面的一块石头，而且虽然说按照代码有时候会移除最后一块石头，但其实这种情况时，就等于是移除最后一块石头之前的未被移除的石头，这是为什么呢？假设是最大距离12，中间石头1块，距离为11，这时他和最后一块石头距离为1。因为要移除最后一块石头时，说明前面的石头之间的距离肯定大于此时的mid，在这种情况移除前面一块石头和移除最后一块石头，最终的最短距离都一定会大于当前的mid，这样子就满足条件了，而我们记录的是移除的石头块数，这都是一样的，在循环里看起来是移除最后一块石头，实际上还是移除前面一块石头。因为前面是要有保留石头才会出现这种情况，要不就直接首尾相减了，此时肯定会大于最后的mid，不会移除任何一块石头，也就不会增加移除的石头块数，不会影响后面的判断。

在判断函数之后，加上二分来缩小距离，就可以得出本题的题解。