POJ 1064 - Cable master

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

概要

N 本のケーブルから，ある一定の長さ l のケーブルを K 本得たい． N 本のそれぞれのケーブルの長さが与えられるので，l の最大値を答える．

制約

• 1 <= N <= 10000
• 1 <= K <= 10000
• 1 <= ケーブルの長さ(メートル) <= 10000

解法

l について整数二分探索．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 bool ok(const vector<long long>& cables, int K, long long len)
 6 {
 7   if (len == 0) {
 8     return true;
 9   }
10   for (vector<long long>::const_iterator it(cables.begin()); it != cables.end() && K > 0; ++it) {
11     K -= *it / len;
12   }
13   return K <= 0;
14 }
15 
16 int main()
17 {
18   int N, K;
19   scanf("%d %d", &N, &K);
20   vector<long long> cables(N);
21   long long right = 0LL;
22   for (int i = 0; i < N; i++) {
23     double d;
24     scanf("%lf", &d);
25     cables[i] = 100LL*d;
26     right = max(right, cables[i]);
27   }
28   long long left = 0;
29   while (left < right) {
30     if (left+1 == right) {
31       if (ok(cables, K, right)) {
32         left = right;
33       }
34       break;
35     }
36     const long long mid = (left + right) / 2LL;
37     if (ok(cables, K, mid)) {
38       left = mid;
39     } else {
40       right = mid;
41     }
42   }
43   printf("%lld.%02lld\n", left/100, left%100);
44   return 0;
45 }