记录编号	210441	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]跳石头	最终得分	100
用户昵称	yhr	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2015-11-27 19:19:40	内存使用	0.43 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int l,n,m,mid,x,y,ans=0,cnt=0;
int k,col[50005],ok;
int main() {
	freopen("2015stone.in","r",stdin);
	freopen("2015stone.out","w",stdout);
	scanf("%d%d%d",&l,&n,&m);
	col[0]=0;
	for(int i=1; i<=n; i++) {
		scanf("%d",&col[i]);
		if(i==n) col[i+1]=l;
	}
	x=0;
	y=l;
	for(;;) {
		cnt=0;
		ok=1;
		int last=0;
		if(x>y) break;
		mid=x+(y-x)/2;
		for(int i=1;i<=n+1;i++){
			if(col[i]-last<mid){
				cnt++;
			}
			else{
				last=col[i];
			}//printf("%d %d\n",mid,cnt);
			if(cnt>m) {ok=0;break;}
		}
		if(ok) {x=mid+1;ans=mid;}
		else y=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}