题目描述：

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

输入格式：

输入文件第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。

接下来 N 行，每行一个整数，第 i 行的整数 D_iDi​（0 < D_i < L0

输出格式：

输出文件只包含一个整数，即最短跳跃距离的最大值。

实例：

输入：

25 5 2

2

11

14

17

21

输出：

4

解题思路：

“最短跳跃距离的最大值”，其中“最短跳跃距离”是指从起点到终点，每两个相邻石头之间距离的最小值。“最短跳跃距离的最大值”是因为在从起点到终点的过程，由于有无移走石头，移走哪个石头的影响，从而导致多种情况，有多种“最短跳跃距离”。（这个点迷糊了好久，弄清楚这个下面就好写了）

采用的是二分法，具体分析都在注释里啦。不清楚二分法怎么写的可以看一下我的另一篇：

整数二分——数的范围_I_Like_S_的博客-CSDN博客

参考代码：

#include

using namespace std;

const int N = 50005;

int a[N];

int L, n, m;

int check(int k)//判断这个最短距离的最大值是否满足移动小于等于m个石头

{

int now = 0;//当前位置

int count = 0;//移石头的次数

for(int i=1;i<=n+1;i++)

{

if (a[i] - a[now] < k) //当前位置到下个石头的距离小于 目前的最短距离，那这个石头就不能留，不然这个差值就是最短距离了。

count++;//移走

else

now = i; //如果差值大于最短距离那就更新位置，继续判断在这个石头和下面石头的差值。

}

if (count <= m) //不止要移走石头，还得看移走的石头是否大于能移走的石头数量，只有这样才是真正的最短距离（其中之一）

return 1;

else

return 0;

}

int main()

{

cin >> L >> n >> m;

for (int i = 1; i <= n; i++) cin >> a[i];

a[n+1] = L;

int ans, b = 0, r = L;

while (b <= r)

{

int mid = (b + r) / 2;

if (check(mid))

{

ans = mid;//这是得到了其中一个最短距离，要找最大的那个，就要在这个基础上找再大一点的

b = mid + 1;//所以找了区间中点的右半部分

}

else//不满足要求,说明这个距离太大了

r = mid - 1;//找这个区间中点的左半部分

}//当while循环结束，也就找到啦！

cout << ans;

return 0;

}