【World Finals】2007 I

【试题编号】
2007 I
【名称】
Water Tanks
【题目大意】
给n个水箱 中间用管道连接 第一个水箱是开口的 往第一个水箱灌水 问能灌多少水
【算法讨论】
考虑把第一个水箱灌满的时候的水压可以让第二个水为到哪 并计算出3~n个水箱当前的水压 然后去算第3个水箱。。。
【时空复杂度】
O(N)
O(N)
【code】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
const double k = 0.097;
int n;
double ta[11], pi[11], h0, dh, v, v0, p, sum;
double get(double b, double c)
{
    return b / 2 - sqrt(b * b / 4 - c);
}
int main()
{
    int test = 0;
    while (scanf("%d", &n), n)
    {
        v = 0;
        for (int i = 0; i < n; ++i)
        {
            scanf("%lf", &ta[i]);
            if (i)
                v += ta[i];
        }
        for (int i = 1; i < n; ++i)
            scanf("%lf", &pi[i]);
        v -= pi[1];
        p = 1;
        sum = pi[1];
        for (int i = 1; i < n; ++i)
        {
            dh = pi[i + 1] - pi[i];
            if (i < n - 1)
                h0 = pi[i + 1] + (p * v / (v - dh) - 1) / k;
            if (h0 > ta[0] || i == n - 1)
            {
                dh = ta[0] - pi[i];
                sum += get(dh + v + 1 / k, dh * v + (1 - p) * v / k);
                break;
            }
            sum += dh;
            p *= v / (v - dh);
            v -= dh;
            h0 = pi[i + 1] + (p * v / ( v - pi[i + 1]) - 1) / k;
            if (h0 > ta[0])
            {
                sum += v - v * p / (1 + (ta[0] - pi[i + 1]) * k);
                break;
            }
            p *= v / (v - pi[i + 1]);
            v -= ta[i];
            v0 = ta[i] - pi[i + 1];
            dh = ta[0] - pi[i + 1];
            sum += pi[i + 1] + get(dh + v0 + 1 / k, dh * v0 + (1 - p) * v0 / k);
        }
        printf("Case %d: %.3f\n\n", ++test, sum + ta[0]);
    }
}