跳石头 题解

这道题是二分套路题中的经典问题 —— 最小值最大化，除此之外还有最大值最小化问题，解法和这个差不太多。

我们先来考虑暴力法如何做，需要枚举n 块石头中选取m石头的所有组合，时间复杂度直接爆炸！

所以需要优雅一点的暴力，同样是枚举，不过我们枚举的是最短距离的最大值d。

对这个临界值进行二分，每次二分都去判断当前最短距离的最大值是否能通过移走 m 个以内的石头达到中位值 mid，如果满足条件，则使 left=mid, 反之使 right=mid-1，因为我们要使最小值尽可能的大，所以当 mid 已经满足条件时我们任然要继续往更大的值进行尝试，另外 mid 如果此时已经满足条件则有可能就是最终答案，所以需要用 left 保存下来。

另外，我们 check 中可以采用贪心思想：

如果当前石头和上一块石头的距离小于 len，则将当前石头拿走。这是因为如果某个最优解中是拿走了上一块石头，那么我们可以改成留下上一块石头，拿走当前这块石头，这样总共拿走的石头数量不变，所以当前选法也是一组最优解。
如果当前石头和上一块石头的距离大于等于 len，则将上一块石头更新成当前这块。
扫描结束后观察拿走的石头数量是否小于等于 m，如果小于等于则满足条件。

AC代码

//运行时间 10ms       超过100%的用户
//运行内存 0.77MB     超过100%的用户
#include<cstdio>
int len, n, m;
int stone[50005];
bool check(int d) {   //检查距离d是否合适
    int num = 0;       //num记录搬走石头的数量
    int pos = 0;       //当前站立的石头
    for (int i = 1; i <= n; ++i)
        if (stone[i] - pos < d)  num++;          //第i块石头可以搬走
        else                  pos = stone[i];   //第i块石头不能搬走
    if (num <= m) return true;  //要移动的石头比m少，满足条件
    else return false;         //要移动的石头比m多，不满足条件
}
int main() {
    scanf("%d%d%d", &len, &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &stone[i]);
    stone[++n] = len;
    int L = 0, R = len, mid;
    while (L < R) {
        mid = L + (R - L + 1) / 2;
        if (check(mid)) L = mid;  //满足条件
        else           R = mid - 1;  //不满足条件，说明mid大了，调小一点
    }
    printf("%d\n", L);
    return 0;
}