POJ2456 Aggressive cows

Aggressive cows

二分，关键是转化为二分！

 1 #include <cstdio>
 2 #include <algorithm>
 3 const int maxn = 1000000005;
 4 const int maxN = 100005;
 5
 6 int N, C;
 7 int a[maxN];
 8 using namespace std;
 9 bool judge(int x) {
10     int s = 0;
11     for (int i = 1; i < C;i++) {
12         int ctr = s+1;
13         while (ctr < N && (a[ctr]-a[s] < x)) {
14             ctr++;
15         }
16         if (ctr==N) {
17             return false;
18         }
19         s = ctr;
20     }
21     return true;
22 }
23 int main(void)
24 {
25     scanf("%d%d", &N, &C);
26     for (int i = 0; i < N; i++) {
27         scanf("%d", &a[i]);
28     }
29     sort(a, a+N);
30     int l = 0, u = maxn, mid;
31     for (;(u-l)>1;){
32         mid = (l+u)/2;
33         if (judge(mid)) {
34             l = mid;
35         } else {
36             u = mid;
37         }
38     }
39     printf("%d\n", l);
40     return 0;
41 }

View Code