原题 : http://poj.org/problem?id=3258
//poj 3258 //大概题意：有一条河流,起点为0，终点为L，中间有N块石头，各石头的位置是已知的,设某个方案中任意两个石头的最小距离为span // 已知最多可以移动M块石头(0<M<=N),但起点和终点不能移动,请问各种移动方案中 最大的span值可以是多少? //思路:我们可以想到结果的范围 一定在0~L之间，所以用二分查找 // 每次得到二分后的中间值span,检查是否合法 // 检查方式：假设span是最小的距离，查看满足span的最多可以存在几块石头,得到结果最多可以有cnt块石头,则被移动的石头数目为N-cnt，根据题意,如果N-cnt<=M即为合法 //二分+贪心 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int s[50001]; int L,N,M; //L 终点位置, N 起点和终点之间的石头数目, M 最多可以移动的石头数目 int cmp(int a,int b) { return a<b; } int check(int span) { int cnt=0; //满足最小距离为span的最多石头数目 int pos=0; //当前位置 for(int i=0;i<N;i++) { if(pos+span<=s[i])//找下一个石头 { pos=s[i];//跳到这个石头 cnt++;//石头数目++ } } if(N-cnt<=M){//这种情况下移动的石头数<最大可移动石头数M return 1; } return 0;//不合法 } int main() { while(~scanf("%d %d %d",&L,&N,&M)) { for(int i=0;i<N;i++) { scanf("%d",&s[i]); } sort(s,s+N,cmp);//从小到大排序 int r=L; int l=0;//结果的范围0~L int rs; while(l<=r)//二分 { int mid=(l+r)/2; if(check(mid)){ rs=mid; l=mid+1; }else{ r=mid-1; } } printf("%d\n",rs); } return 0; } //AC