跳石头

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

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

求最短距离的最大值。

看到最小值最大或最大值最小，第一反应应该就是二分。但是笔者并没有往下想，而是在考虑贪心的做法。其实应该先往下想一想再否定掉一个思路（启发式深搜比广搜优）。

想到二分应该考虑这两点。

1. 是否具有单调性。对于本题而言，明显二分答案具有单调性。如果最短距离的最大值可以是d，那么一定能是一个比d小的值。如果最短距离的最大值不能是d，那么一定不能是一个比d大的值。
2. 如何设计高效的判断函数。对于本题而言，可以贪心的看。从前往后扫一遍，如果当前枚举到的石头和后面一个石头冲突，那么明显的，这两个石头至少要去掉一个。明显的，去掉后面一个对于后面的局势更有利。

还需注意的是，整数二分的时候如果把边界条件写成 while(l<r) 可能会死循环。比如9+10=19,19/2=9。所以要写成 while(l+1<r) 。但是这引入了一个新的问题。比如对于在数组[0,1]上二分的时候，可能无法得到正解（上来就终止循环）。解决方案是使 l+1 。

本题要注意起点和终点的石头没有直接给出，需要自己加上。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50005;

int n;
int len,m;
int a[maxn];
int b[maxn];
int l,r,mid;
//有操作的 
bool jg(int d){
	int now=0;
	for (int i=1;i<=n+1;i++)b[i]=a[i];
	for (int i=0;i<n+1;i++){
		if(b[i+1]-b[i]<d){
			now++;b[i+1]=b[i];
			if(now>m)return false;
		}
	}
	return true;
}

int main(){
	cin>>len>>n>>m;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[n+1]=len;
	l=1;r=len+1;
      	while(l+1<r){
		mid = (l+r)/2;
		if(jg(mid))l=mid;
		else r=mid;
	}
	cout<<l<<endl;
	
	
	return 0;
}