POJ 3258 River Hopscotch（二分答案）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 int len, m, n, a[500005];
 9 
10 inline int check(int x){
11     int cnt = 0, last = 0;
12     for(int i = 1; i <= n + 1; i++){
13         if(a[i] - a[last] < x) cnt++;
14         else last = i;
15     }
16     if(cnt <= m) return 1;
17     return 0;
18 }
19 
20 int main(){
21     while(scanf("%d%d%d", &len, &n, &m) != EOF){
22         memset(a, 0, sizeof(a));
23         a[n + 1] = len;
24         for(int i = 1; i <= n; i++){
25             scanf("%d", &a[i]);
26         }
27         sort(a + 1, a + n + 1);
28         int l = 1, r = len, ans;
29         while(l <= r){
30             int mid = (l + r) >> 1;
31             if(check(mid)) {ans = mid; l = mid + 1;}
32             else r = mid - 1;
33         }
34         printf("%d\n", ans);
35     }
36     return 0;
37 }