[POJ2456]Aggressive cows（贪心，二分查找）

题目链接：http://poj.org/problem?id=2456

二分+贪心

这是个求最小值最大的问题，我们二分从0到inf的数d，作为两头牛放置的距离不小于d，然后贪心判断。

首先要对x从小到大进行排序，接下来固定x[0]处必有一头牛，然后间距不小于d的时候，可以放置，一直放置，直到所有牛舍均被遍历O(n)。

如果牛被完全放置，那么返回true，并且向右确定边界，反之向左确定。

ac代码(32ms)：

 1 #include <cstdio>
 2 
 3 const int maxn = 100010;
 4 const int INF = 1 << 30;
 5 int n, m;
 6 int x[maxn];
 7 int ll[maxn>>1], rr[maxn>>1];
 8 
 9 inline bool scan_d(int &x) {
10         char in;bool IsN=false;
11         in=getchar();
12         if(in==EOF) return false;
13         while(in!='-'&&(in<'0'||in>'9')) in=getchar();
14         if(in=='-'){IsN=true;x=0;}
15         else x=in-'0';
16         while(in=getchar(),in>='0'&&in<='9') {
17                 x*=10,x+=in-'0';
18         }
19         if(IsN) x=-x;
20         return true;
21 }
22 
23 inline void printf_d(int a) {
24     if(a > 9) {
25         printf_d(a / 10);
26     }
27     putchar(a % 10 + '0');
28 }
29 
30 void merge(int *x, int p, int m, int q) {
31     int n1 = m - p + 1;
32     int n2 = q - m;
33     int i = 0, j = 0;
34     for(int ii = 0; ii < n1; ii++) ll[ii] = x[p+ii];
35     for(int ii = 0; ii < n2; ii++) rr[ii] = x[m+ii+1];
36     while(i < n1 && j < n2) {
37         if(ll[i] <= rr[j]) x[p++] = ll[i++];
38         else x[p++] = rr[j++];
39     }
40     while(i < n1) x[p++] = ll[i++];
41     while(j < n2) x[p++] = rr[j++];
42 }
43 
44 void mergesort(int *x, int p, int q) {
45     if(p < q) {
46         int m = (p + q) >> 1;
47         mergesort(x, p, m);
48         mergesort(x, m+1, q);
49         merge(x, p, m, q);
50     }
51 }
52 
53 bool ok(int d) {
54     int cow = 1;
55     int tmp = x[0];
56     for(int i = 1; i < n; i++) {
57         if(x[i] - tmp >= d) {
58             cow++;
59             tmp = x[i];
60         }
61     }
62     if(cow >= m) {
63         return true;
64     }
65     return false;
66 }
67 
68 int main() {
69     // freopen("in", "r", stdin);
70     while(scan_d(n) && scan_d(m)) {
71         for(int i = 0; i < n; i++) {
72             scan_d(x[i]);
73         }
74         mergesort(x, 0, n-1);
75         int ll = 0, rr = INF;
76         while(rr - ll > 1) {
77             int mm = (ll + rr) >> 1;
78             if(ok(mm)) {
79                 ll = mm;
80             }
81             else {
82                 rr = mm;
83             }
84         }
85         printf_d(ll);
86         putchar('
');
87     }
88 }

对于本题取ll还是rr的问题，如果拿不准可以每次更新ll,rr的时候同时选择是否更新ans，这样就不用纠结了。二分查找的限界也可以很无脑地记住。

 1 const int maxn = 100010;
 2 int n, c, ans;
 3 int x[maxn];
 4 
 5 bool ok(int d) {
 6     int cow = x[1];
 7     int cnt = 1;
 8     for(int i = 2; i <= n; i++) {
 9         if(x[i] - cow >= d) {
10             cnt++;
11             cow = x[i];
12         }
13     }
14     return cnt >= c;
15 }
16 
17 int main() {
18     // freopen("in", "r", stdin);
19     while(~scanf("%d %d", &n, &c)) {
20         for(int i = 1; i <= n; i++) {
21             scanf("%d", &x[i]);
22         }
23         int ll = 0;
24         int rr = 0x7f7f7f7f;
25         ans = 0x7f7f7f7f;
26         sort(x+1,x+n+1);
27         while(ll <= rr) {
28             int mm = (ll + rr) >> 1;
29             if(ok(mm)) {
30                 ll = mm + 1;
31                 ans = mm;
32             }
33             else rr = mm - 1;
34         }    
35         printf("%d
", ans);
36     }
37     return 0;
38 }