P4775 跳石头比赛（提高）

河里有起点和终点（相距 S），中间还有 N 块岩石，每块离起点的距离已知。农夫最多可以搬走 M 块岩石（起点和终点不能搬），问搬完之后从起点一路跳到终点，最短的一段跳跃距离最大能是多少。

解题思路

1. 先想清楚要二分什么。 如果定一个"最短跳跃距离" d，那么相邻两块保留的岩石（包括起点和终点）之间的距离必须至少是 d，距离不够的岩石就得搬走。d 越大，需要搬走的岩石就越多。所以"需要搬走的岩石数不超过 M"这件事，随 d 变大而越来越难满足，满足单调性，可以用二分答案。

2. 怎么检查一个 d 行不行。 从起点开始，用变量 current 记上一块保留的岩石位置。从头扫过每一块岩石：如果这块岩石到 current 的距离小于 d，就把它搬走（搬走的数量加 1）；否则保留它，把 current 更新成这块岩石的位置。扫完之后，还要检查终点 S 到 current 的距离，如果小于 d，说明最后这块也得处理掉，搬走数量再加 1。如果总共搬走的数量 <= M，说明 d 是可行的。

3. 二分找最大可行 d。 low = 0，high = S（整个河道的距离）。每次取 mid = (low + high + 1) / 2 检查。可行就 low = mid 试试更大的，不可行就 high = mid - 1。

4. 具体例子。 S = 25，N = 5，M = 2，岩石在 2、11、14、17、21。检查 d = 4：依次搬走 2 和 14，留下 11、17、21，跳跃距离是 11、6、4、4，最小是 4，一共搬 2 块没超过 M，可行；检查 d = 5 时需要搬 3 块，超过 M，不行。所以答案就是 4。

5. 边界情况。 如果中间一块岩石都没有（N = 0），从起点到终点只有一跳，最短跳跃距离就是 S，二分也能正确得到 S。

参考代码

// 跳石头比赛：二分答案，求移走至多M块岩石后最短跳跃距离的最大值
#include <cstdio>
using namespace std;
int rockDist[50005]; // 每块岩石与起点的距离

int main(){
    int s, n, m;
    scanf("%d%d%d", &s, &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d", &rockDist[i]);
    }
    int low = 0, high = s;
    // 二分答案：最短跳跃距离越大，需要搬走的岩石就越多
    while(low < high){
        int mid = (low + high + 1) / 2;
        int current = 0; // 上一块保留的岩石位置（起点视为0）
        int removed = 0; // 需要搬走的岩石数量
        for(int i = 0; i < n; i++){
            if(rockDist[i] - current < mid){
                removed++; // 距离太近，搬走这块岩石
            } else {
                current = rockDist[i]; // 距离够远，保留这块岩石
            }
        }
        if(s - current < mid){
            removed++; // 最后一段到终点的距离也要检查
        }
        if(removed <= m){
            low = mid;      // 搬走的数量没超过m，可以试试更大的距离
        } else {
            high = mid - 1; // 搬走太多，只能缩短距离
        }
    }
    printf("%d\n", low);
    return 0;
}

复杂度分析

二分答案的范围是 [0, S]，S 最大 10^9，约 30 次检查；每次检查要扫一遍 N 块岩石（N ≤ 50000），所以时间复杂度是 O(N log S)，大约 150 万次运算，完全来得及。空间上用一个数组存每块岩石的距离，空间复杂度是 O(N)。