题解：P2678 [NOIP2015 提高组] 跳石头

封面

题目洛谷

思路：

二分答案。

要求找最小值最大，所以考虑二分。

对于每次二分的 midmid 最小需要跳跃的距离，进行一次检查，对于检查函数，为了确定编号为 ii 的岩石之前没有被删除的岩石是哪个，要定义一个 lastlast 存上一个没有被删除的岩石的编号，每次对比 DiD_i 和 DlastD_{last} 的差，如果小于我们二分到的距离就说明要移走，否则不要移走更新 lastlast 为 ii，如果要移走的岩石小于等于最多可以移走的岩石 mm 说明这种情况是可能的，否则不可能。

答案为每个满足的 midmid 中的最大值。

注意起点和终点要在数组里，DD 数组输入时不会有终点和起点，自行要添加。

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL l,n,m;
LL a[50003],maxx;
bool check(LL mid){
	int last=0,del=0;
	for(int i=1;i<=n;i++){
		if(a[i]-a[last]<mid){
			del++;
		}
		else last=i;
	}
	return del<=m;
}
int main(){
	cin>>l>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];// 代码中的数组 a 为题目中的数组 D
	sort(a+1,a+1+n);
	a[++n]=l;
	LL r=l,l=1,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){
			l=mid+1;
			maxx=mid;
		}
		else r=mid-1;
	}
	cout<<maxx;
	return 0;
}