问题分析

什么是最短跳跃距离？

每个选手最终都会跳到终点，由于石头的布置不是均匀的，有时候两个石头间离得很远，那么选手就要跳的远些；而有时两个石头又离的很近，选手只需要跳很短的距离就行。这个时候就会产生一个最短跳跃距离

最长的最短跳跃距离是什么意思？

正如题意所说，为了加大难度，如果两个石头间里的很近，那么我们需要一走其中一块石头，让选手跳的远些，这种行为就加长了最短的跳远距离。因此最大的最短距离就是在选手跳到终点的过程中，在题目要求的情况下 我们要尽可能多的移走石头，最大限度的加长选手的最短跳跃距离

如何求解？

显然 如果想针对每种输入去不断从1枚举一个最短跳跃距离，是较为复杂的，而且非常容易超时。那我们不妨换一个思路：我们能不能针对某一个距离，去判定他能不能满足条件 ，换句话说：对于一个距离x，我们把它作为最长的最短判断距离，然后让选手进行跳跃，只要有两个石头间的距离小于这个x，我们就把这两个石头中的一个移走，最后看一下我们移走的石头数量是否满足条件，这样我们就把枚举变成了判定问题，判定问题当然要比枚举问题好求解。

如何找这个x？

注意到每个石头的里起点越来越远，因此我们认为这个石头排列是有序的。既然有序，且要找一个尽可能大的值，那么二分法就是很好的选择。

具体求解过程

上面已经分析得知，利用二分法把枚举转为判定问题的算法叫做二分答案。

int main()

{

cin >> L >> N >> M; //L为比赛长度，N为石头数量,M为最多移走的石头个数
ll ans = 0; //ans为最长的最短跳跃距离
for (int i = 0; i < N; i++) { cin >> a[i]; }//将每个石头里原点的距离放入数组
a[N] = L; //注意：终点处石头离起点的距离没有给出，需要手动把距离放入数组
//下面是二分查找，直接用y总模板
ll l = 1, r = L+1;
while (l < r)
{
    int mid = (l + r + 1) >> 1;
    if (check(mid)) //这里的check()函数就是判断每一种最短最大距离是否成立
    {
        l = mid;//如果满足题意就看还有没有更长的最短距离
        ans = mid;//成立就把该值放入ans中
    }
    else { r = mid - 1; }//找大了往小的找
}
cout << ans;
return 0;

}

//下面是判定函数的实现

bool check(ll mid)

{

int cnt = 0; //表示对于一个长度x，一共需要的移走的石头数量
int last = 0; //last表示上一块石头里起点的距离，一开始为0

for (int i = 0; i <= N; i++)//针对每一个长度模拟整个比赛流程
{
  
    if (a[i] - last >= mid)//只要两块石头间长度大于判定长度，就认为不用移走其中一块
    {
        last = a[i];//将last变成上一块石头
    }
    else
    {
        cnt++;//否则就移走一块石头，且不更新 last。
    }
}
return cnt <= M;//最后返回判断真假即可

}