给定起点和终点之间的距离 L ，在起点和终点之间存在 n 个点，给出这 n 个点距离起点的距离，求把这n个点中去掉m个点后剩余点之间可能的最小值的最大值（即求 n-m 个点之
间距离最小值的最大值） 。
首先知道结果必然存在于在不操作的最小值和L之间，答案范围确定。
然后就是给定middle含义： 比最小值略小的一个值。
用一个for循环进行处理，最后得到的值blocks满足小于等于middle的需要拿走的最小石头数，证明略。
如果拿走的最小石头数依然是大于middlem，即可以肯定的是当前石头之间距离大于等于middle时，这个middle是偏大的，需要小一点，但是最小值却很有可能是middle(middle
是小于最小值的)。
/*2015-05-15 09:19 Binitray_find: Caution: middle = ( l + h)/2, cant use l = middle? EPS: l = middle,h = middle+1, middle = (middle + middle+1)/2 = middle,cause TLE! Caution: the looper is (L < H) or (L <= H)? ANS: must be careful the meanning of the program!
------------------141ms--------------------------
最优 110ms */ #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int between_of[50005],n; int find_two(int l,int h,int m){ while(l < h){//当 l == h 的时候，答案是否会是 l+1 ,放回middle值，因为在这个过程中，可能存在(middle-1)，的情况 int middle = (l+h)/2; int s = 0; int blocks = 0; for(int i = 1;i<=n+1;i++ ){ if((s+=between_of[i] ) <= middle)blocks++;//最少可以变化的是middle else s = 0; } if(blocks <= m)l = middle+1;//避免l = middle的处理，所以为了防止出现l = middle，需要从意义上进行转换 else h = middle;//答案可能是middle，因为从意义上来思考，middle是（最小值-1），因为是middle的时候需要将石头去掉，因此最小肯定至少大于middle } return l; } int main(){ int l,m; while(~scanf("%d%d%d",&l,&n,&m)){ int dis_s[50005]; dis_s[0] = 0; for(int i = 1;i<=n;i++){ scanf("%d",&dis_s[i]); } dis_s[n+1] = l; sort(dis_s,dis_s+n+2); int min_ = 0x3f3f3f3f; for(int i = 1;i<n+2;i++){ between_of [i] = dis_s[i] - dis_s[i-1]; min_ = min(min_,between_of[i]); } printf("%d ",find_two(min_,l,m)); } }