2015D2T1 跳石头

2015D2T1 跳石头

problem

数轴上(m)个点，可以移走(n)个点，求最短跳跃距离最长。

solution

最短xxx的最长，想到二分。可以(log)复杂度。先寻找一个单调性，每次跳(mid)距离，看跳了几个石头，少了就长度短点，长了就长度长点。

code

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
long long read(){
	int a=0,op=1;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-') op=-1;c=getchar();}
	while(c>='0'&&c<='9'){a*=10,a+=c^48,c=getchar();}
	return a*op;
}
const int maxn=6e4+5;
long long l,m,n,ll,rr,mid,now,i,s,ans;
long long d[maxn];
int main(){
	l=read(),n=read(),m=read();
	for(long long i=1;i<=n;i++) d[i]=read();
	ll=0;rr=l;
	while(ll<=rr){
		mid=(ll+rr)>>1;
		now=0;s=0;
		for(int i=1;i<=n;i++){
			if(d[i]-d[now]<mid) s++;
			else now=i;
		}
		if(s<=m) ans=mid,ll=mid+1;
		else rr=mid-1;
	}
	printf("%lld",ans);
	return 0;
}