跳石头

解题思路

一段长为 L 的路径上有 N + 2 个点，其中两个点位于路径端点，第 i 个点与第 i+1 个点之间的距离为 jump[i]。
最多可以消除 M 个点，但不能消除路径两边的端点。求相邻两点之间最短的距离的最大值。

对相邻两点之间最短距离 mid 使用二分法。显然，mid >= 1 且 mid <= L。
如果 jump[i] < mid，消除第 i+1 个点，直至第 i 个点与其后相邻的点的距离 >= mid 停止消除，将消除点的次数累加计入 k。
如果 k > M，表示 mid 过大；否则 mid 这个距离是可以实现的。

C++代码

#include<cstdio>
#include<vector>
using namespace std;

int main(){
    int L, N, M;
    scanf("%d%d%d", &L, &N, &M);
    vector<int> D(N+2, 0);
    vector<int> jump(N+1);
    for(int i=1; i<=N; ++i){
        scanf("%d", &D[i]);
        jump[i-1] = D[i] - D[i-1];
    }
    D[N+1] = L;
    jump[N] = L - D[N];

    int left = 1;
    int right = L;
    int ans = 1;
    while(left <= right){
        int mid = left + (right-left)/2;
        int k = 0;
        for(int i=0; i<N+1; ++i){
            if(jump[i] < mid){
                int j=i+1;
                int sum = jump[i] + jump[j];
                ++k;
                while(sum < mid){
                    ++j;
                    ++k;
                    sum += jump[j];
                }
                i = j;
            }
        }
        if(k <= M){
            ans = mid;
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}