题解 P3853 【[TJOI2007]路标设置】

#include<bits/stdc++.h>
using namespace std;
int l,r,len,n,k,maxx,a[100005];
//通过计算可以发现 对一个给定的距离len而言 中间分成若干个长度不大于x的段的个数为 len/x 如果len为x的倍数 则为len/x-1 
bool check(int x){
	int tmp=0;
	for (int i=2;i<=n;i++){
		tmp+=(a[i]-a[i-1])/x;
		if ((a[i]-a[i-1])%x==0) tmp--;
	}
	if (tmp<=k) return true;
	return false;
}
int main(){
	scanf("%d%d%d",&len,&n,&k);
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		maxx=max(maxx,a[i]-a[i-1]);
	}
	l=1;
	r=maxx;
	while (l<r){
		int mid=(l+r)/2;
		if (check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d
",l);
	return 0;
}