poj 3258 River Hopscotch 二分

 1 /**
 2 大意：给定n个点，删除其中的m个点，其中两点之间距离最小的最大值
 3 思路： 二分最小值的最大值---〉t，若有距离小于t，则可以将前面的节点删除；若节点大于t，则继续往下查看
 4           若删除的节点大于m，说明t，过于大，需要减小；若删除的节点小于m说明t过于小了，t需要增大
 5 **/
 6 #include <iostream>
 7 #include <algorithm>
 8 using namespace std;
 9 long long c[50050];
10 int main()
11 {
12     long long l,n,m;
13     cin>>l>>n>>m;
14     for(int i=1;i<=n;i++)
15         cin>>c[i];
16     c[0] =0;
17     c[n+1] = l;
18     n = n+2;
19     sort(c,c+n);
20     long long minn =c[1]-c[0];
21     for(int i=2;i<n;i++){
22         minn = min(minn,c[i]-c[i-1]);
23     }
24     long long low = minn,high = l;
25     long long mid;
26     while(low<=high){
27         mid = (high+low)>>1;
28         int cnt =0;
29         int s=0,e=1;//start 开始节点，end，最后节点
30         while(e<n){
31             if(c[e]-c[s]>=mid)
32                 s =e,e++;
33             else
34                 e++,cnt++;
35         }
36         if(cnt>m)
37             high = mid-1;
38         else
39             low = mid +1;
40     }
41     cout<<high<<endl;
42     return 0;
43 }