POJ 1434 - Fill the Cisterns!

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

概要

n 個の水槽があり，すべての水槽が体積の無視できるパイプで繋がっている．

各水槽には

• 水槽の底面がある高さ b
• 水槽の高さ h
• 水槽の幅 w
• 水槽の奥行 d

が設定されている．

これらに体積 V の水を入れたとき，水位の高さはどうなるかを答える．

制約

• 1 <= n <= 50000
• 0 <= b <= 10^6
• 1 <= h * w * d <= 40000
• 1 <= V <= 2 * 10^9

解法

POJ 3334 - Connected Gheeves の簡単なバージョン．

水位に関して二分探索．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 struct cistern { int b, h, s; };
 6 
 7 double volume(const cistern *v, int N, double h)
 8 {
 9   double vol = 0.0;
10   for (int i = 0; i < N; i++) {
11     if (v[i].b < h) {
12       vol += v[i].s * (min(double(v[i].b + v[i].h), h) - v[i].b);
13     }
14   }
15   return vol;
16 }
17 
18 int main()
19 {
20   int T;
21   scanf("%d", &T);
22   while (T-- > 0) {
23     int N;
24     scanf("%d", &N);
25     static cistern v[50000];
26     int ttl = 0;
27     double left = 1e10, right = 0.0;
28     for (int i = 0; i < N; i++) {
29       int w, d;
30       scanf("%d %d %d %d", &v[i].b, &v[i].h, &w, &d);
31       v[i].s = w*d;
32       ttl += v[i].s*v[i].h;
33       left = min(left, double(v[i].b));
34       right = max(right, double(v[i].b + v[i].h));
35     }
36     int V;
37     scanf("%d", &V);
38     if (V > ttl) {
39       puts("OVERFLOW");
40     } else {
41       for (int i = 0; i < 100; i++) {
42         const double mid = (left + right)/2.0;
43         if (volume(v, N, mid) < V) {
44           left = mid;
45         } else {
46           right = mid;
47         }
48       }
49       printf("%.2f\n", (left + right)/2.0);
50     }
51   }
52   return 0;
53 }