↓ 跳过正文
题解：P2678 [NOIP2015 提高组] 跳石头

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

xyx404
作者
xyx404
Have a nice day.
目录

题目

思路：
#

二分答案。

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

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

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

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

代码：
# 

#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;
}