POJ 2456 - Aggressive cows

http://poj.org/problem?id=2456

概要

N 個の一直線に並んだ小屋がある．i 番目の小屋は x[i] の位置にある．

これらの小屋に C 頭の牛を，隣りの牛との距離の最小値が最大になるように入れたい． そのときの距離の最小値を答える．

制約

• 2 <= C <= N <= 100000
• 0 <= x[i] <= 1000000000

解法

二分探索．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 bool ok(const long long *a, int N, int C, long long d)
 6 {
 7   const long long *p = a;
 8   for (int i = 1; i < C; i++) {
 9     const long long x = *p;
10     p = lower_bound(p, a+N, x+d);
11     if (p == a+N) {
12       return false;
13     }
14   }
15   return true;
16 }
17 
18 int main()
19 {
20   int N, C;
21   scanf("%d %d", &N, &C);
22   static long long a[100000];
23   for (int i = 0; i < N; i++) {
24     scanf("%lld", &a[i]);
25   }
26   sort(a, a+N);
27 
28   long long left = 1LL, right = 1000000000LL;
29   while (left < right) {
30     const long long mid = (left + right + 1LL) / 2LL;
31     if (ok(a, N, C, mid)) {
32       left = mid;
33     } else {
34       right = mid-1LL;
35     }
36   }
37   printf("%lld\n", left);
38   return 0;
39 }