虎鲸der二分题解：

是的没错勤劳der虎鲸又来告你怎么做了

这次写个详细的：）

下面如果你知道这题用二分可以不看：）

———————————————————————————————————————————

这道题如果要使用暴力搜索直接求解会严重超时。实际上，我们可以发现，这个所谓的最短跳跃距离显然不能超过一个范围，而这个范围题目上已经给了出来。也就是说，答案是有一个确定的范围限制的，我们就可以考虑一种另外的方法去解决——二分答案，并去验证答案是否可行。 ——————————————————————————————————————————

不知道二分的可以先去学一下，不然你看不懂。。这里不再介绍二分（！！

——————————————————————————————————————————

这题的二分check函数主要大意是开始你在i(i=0)位置，下一步判断当前跳跃的距离，如果这个跳跃距离比二分出来的mid小，那这就是一个不合法的。如果跳跃距离比最短更短是显然不合法。移走之后要怎么做？先把计数器加上1，再考虑向前跳。去看移走之后的下一块石头，再次判断跳过去的距离，如果这次的跳跃距离比最短的长，那么这样跳是可以的，如果跳过去的距离不合法就再拿走，这样不断进行这个操作，直到i = n+1，（这里千万要注意不要把n认为是终点，实际上从n还要跳一步才能到终点）。

然后查看计数器的值，这个值是我们以mid作为答案需要移走的石头数量，如果超了就返回false，不超就返回true。

———————————————————————————————————————————

大概是这样，看不懂看下面的代码：

#include<bits/stdc++.h>
using namespace std;
int len,n,m;
int a[50002]={0};
//如果返回true表示mid小了， 
//否则表示mid大了。 
bool check(int mid){
	int s=0;
	int x=0;
	for(int i=1;i<=n+1;i++){
		if(a[i]-a[x]<mid){
			s++;
		}
		else{
			x=i;
		}
	}
	if(s>m) return 0;
	return 1;
}
int main(){
	cin>>len>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[n+1]=len;
	int l=1,r=len;
	int ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			l=mid+1;//走到这里，看来是可行解，我们尝试看看是不是有更好的可行解
			ans=mid;
		}
		else{
			r=mid-1;//噫，你找了个非法解，赶紧回到左半边看看有没有可行解
		}
	}
	cout<<ans;
	return 0;
} 

这个还看不懂的再去章鱼堡学一下二分吧

虎鲸不会帮你（？