http://poj.org/problem?id=3258
题意理解起来很别扭，觉得自己描述的会让人搞不懂，建议去搜一下正规的解释。
1 #include <stdio.h> 2 #include <math.h> 3 #include <algorithm> 4 #include <stdlib.h> 5 const int N=100010; 6 using namespace std; 7 int main() 8 { 9 int L,n,m,d[N]; 10 scanf("%d %d %d",&L,&n,&m); 11 d[0] = 0;//第一块石头的距离 12 d[n+1] = L;//最后一块石头的距离 13 for (int i = 1; i <= n; i++) 14 { 15 scanf("%d",&d[i]);//每一块石头离原点的距离 16 } 17 sort(d,d+n+1);//将距离按升序排序 18 int Min = d[1]; 19 for (int i = 1; i <= n+1; i++) 20 { 21 int dis = d[i]-d[i-1]; 22 if (dis < Min) 23 Min = dis;//求出最小距离作为下限 24 } 25 int low = Min; 26 int high = L; 27 while(low <= high)//二分 28 { 29 int mid = (low+high)/2;//尝试每次以mid为两石头间的最小距离 30 int ans = 0,cnt = 0; 31 for (int i = 1; i <= n+1; i++) 32 { 33 ans+=(d[i]-d[i-1]); 34 if (ans < mid) 35 cnt++;//统计需要移除的石头数 36 else 37 ans=0; 38 } 39 if (cnt <= m) 40 low = mid+1;//增加上限 41 else 42 high = mid-1;//减小下限 43 } 44 printf("%d ",high); 45 return 0; 46 }