题目链接：

https://ac.nowcoder.com/acm/problem/16462

题面：

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

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

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

输入描述：

输入文件第一行包含三个整数 L,N,M ，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。 接下来 N 行，每行一个整数，第 i 行的整数 Di(0<Di<L)表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出描述：

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

input：
25 5 2
2
11
14
17
21

output:
4

样例说明:

将与起点距离为 2 和14 的两个岩石移走后，
最短的跳跃距离为 4
（从与起点距离17的岩石跳到距离 21的岩石，
  或者从距离 21 的岩石跳到终点）。

分析：

刚开始一直把注意力聚焦在去除石头的最佳策略上，发现纯贪心似乎不行，因为随着石头被不断拿走，最短距离动态变化，正向模拟石头被移走的各种状态应该会超时（这行我瞎写的(@ _@)）。

第一眼看题，难以直接确定解，可以采取二分枚举答案+检验的思想将求解类问题转换为验证类问题。

对于移走的岩石数，我们自然希望是越大越好，这样，最短的相邻石头距离才可能更大，但是不能超过组委会能移走的最大数量。

对于二分的判定条件 check()函数 的说明：

  • check() 函数检验 mid 是否可行，每次小于 mid 的石头会被拿掉

即：

  • 我们假设 mid 可行（假设相邻石头的最短距离为 mid）， 验证 在 相邻石头的最短距离为 mid 的情况下，（不满足这个距离的石头将被拿走） 被拿走的石头数 是否大于 组委会能移走的最大数量m

若大于，则说明假设的被拿走的石头数太多，说明 mid 值太大， 要在更小的值中寻找答案 return false; -> right = mid - 1;

若小于等于，则说明假设的被拿走的石头数合法，说明 mid 值 及其之前的值都合法， 可以去更大的值中寻找更大的最优解答案 return true; -> left = mid + 1;

也即：

  • 以 石头的最大移走量m 为指标， 验证 ：在 当前二分枚举的答案mid（假定的最短的相邻石头距离） 下， （统计 有多少石头的距离是不合法的（需要被拿掉的石头数cnt）） 是否恰好能达到 石头最大移走量m 指标

若数量能超标（需要被拿掉的石头数 cnt 大于 组委会的石头的最大移走量m）， 说明 这个二分枚举出来的答案太大了，要在更小的值中找答案 return false; -> right = mid - 1;

若数量在石头的最大移走量m 之内， 说明 当前的 mid 值 达标，即：小于等于 mid 的值都达标，要向 mid 之后的区间找更大的最优解答案 因此要在更大的值中找答案 return true; -> left = mid + 1;

代码：

#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4+7;
int distant[maxn] = {};
int m, n;
ll l;

bool check(ll mid) {	
	int cnt = 0;   // 统计当前假设的相邻石头间的最短距离 mid 下，为满足此假设而需要去掉的石头数
	int pos = 0;   // 上一块石头的位置
	for (int i = 1; i <= n; i++) {  // 枚举每一块石头
		if (distant[i] - pos < mid)  // 如果当前石头和上一块石头的距离 比 假设的相邻石头间的最短距离 mid 小，则把当前石头移走，pos还是上一块石头的位置			
			cnt++;
		else 
			pos = distant[i];  // 否则当前石头不用移走，pos = 当前石头
	}
	if (cnt > m)   // 若 为满足此假设而需要去掉的石头数 超过 组委会的能移走的最大石头数，则 mid 值非法
		return false;
	else 
		return true;
}

int main () {
	
	cin >> l >> n >> m;
	
	for (int i = 1; i <= n; i++) cin >> distant[i];
	
	// 这些岩石按与起点距离从小到大的顺序给出，原数组已经有序
	
	// 按照二分枚举答案，并验证答案的可行性，以此不断逼近最终的正确最大值的答案
	
	ll left = 1, right = l;
	while (left <= right) {  // 固定格式
		ll mid = (left + right) >> 1;
		if (check(mid)) left = mid + 1;
		else right = mid - 1;
	}
	
	cout << left - 1 << endl;
	return 0;
}