二分搜索 POJ 2456 Aggressive cows

 1 /*
 2     二分搜索：搜索安排最近牛的距离不小于d 
 3 */
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <cmath>
 7 using namespace std;
 8 
 9 const int MAXN = 1e5 + 10;
10 const int INF = 0x3f3f3f3f;
11 int x[MAXN];
12 int n, m;
13 
14 bool check(int d)   {
15     int last = 1;
16     for (int i=1; i<=m-1; ++i)    {
17         int cur = last + 1;
18         while (cur <= n && x[cur] - x[last] < d)    cur++;
19         if (cur == n + 1)   return false;
20         last = cur;
21     }
22     return true;
23 }
24 
25 int main(void)  {       //POJ 2456 Aggressive cows 
26     //freopen ("POJ_2456.in", "r", stdin);
27 
28     while (scanf ("%d%d", &n, &m) == 2)   {
29         for (int i=1; i<=n; ++i)    {
30             scanf ("%d", &x[i]);
31         }
32 
33         sort (x+1, x+1+n);
34         int l = 0, r = INF;
35         while (l + 1 < r)   {
36             int mid = (l + r) >> 1;
37             if (check (mid))    l = mid;
38             else    r = mid;
39         }
40         printf ("%d
", l);
41     }
42 
43     return 0;
44 }
编译人生，运行世界！