跳石头_(二分，贪心)

原题链接：P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：跳石头，有起点终点和 n 个石头，从石头里拿走 m 个，使得最短的跳跃距离最长，问最长是多少

思路

是还没有见识过的思路

最短的跳跃距离其实不好找，如果动态的维护数组，挑去石头后更新再挑去的话时间复杂度高，不是优解

题目的范围确定，即起点到终点的距离，可以二分查找答案，找到之后验证答案的正确性

验证 ，只是验证的话其实可以通过查找距离长于当前设定最短距离的石头，直接删去，并入到其下一个石头的间隔，如果是终点不符的话需要去除其前面的石头，检查去掉的石头数量是否超过要求的数量

其中，终点去除前面石头的代码没有实现，数据还是仁慈了

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 5e4 + 10;
 
int len, n, m;
int a[N];
int ans;
 
 
//二分找答案，判断对错
bool judge(int x)
{
    vector<int> t(a, a + n + 1);
 
    int cnt = 0;
    for(int i = 0; i < t.size(); i ++)
    {
        //一旦小于最短最长距离，就直接去掉
        if(t[i] < x)
        {
            t[i + 1] += t[i];
            cnt ++;
        }
        if(cnt > m)  return false;
    }
 
    return true;
}
 
 
 
int erfen()
{
    int l = 1, r = len;
 
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(judge(mid)) l = mid;
        else r = mid - 1;
    }
    
    return r;
}
 
 
int main()
{
    cin >> len >> n >> m;
 
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        a[i - 1] = a[i] - a[i - 1];
    }
    a[n] = len - a[n];
 
    ans = erfen();
 
    cout << ans << endl;
 
    return 0;
}