题解：SP110 CISTFILL - Fill the Cisterns

ggc123 · 2025-08-01 14:54:40 · 题解

思路

对于本题而言，直接通过这些水箱求出答案过于困难。但是不难发现：水位越高，这个容器装的水越多（二分的单调性）。由此可以得到本体考察的是二分。

我们二分答案，对于每一个我们二分出来的答案，去对比当前水位装下的水的体积和给定体积的大小关系。

对于水溢出的情况，我们只需验证所有水箱的容积是否小于水的体积即可。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 50005;

struct A {
    int b, h, w, d;
} a[N];
int T, n, v;

bool check(double x) {
    double cnt = 0;
    for (int i = 1; i <= n; i++)
        cnt += min(max(x - a[i].b, 0.0), (double)a[i].h) * a[i].d * a[i].w;
    return cnt >= v;
}
bool flag() {
    double cnt = 0;
    for (int i = 1; i <= n; i++) cnt += a[i].h * a[i].d * a[i].w;
    return cnt >= v;
}

signed main() {
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i].b >> a[i].h >> a[i].w >> a[i].d;
        cin >> v;

        if (!flag()) {
            cout << "OVERFLOW \n";
            continue;
        }

        double L = 0, R = 2e6, mid, ans;
        while (abs(R - L) >= 1e-5) {
            mid = (L + R) / 2.0;
            if (check(mid))
                ans = R = mid;
            else
                L = mid;
        }
        cout << fixed << setprecision(2) << ans << "\n";
    }

    return 0;
}