解题思路

这道题目要求我们计算在给定的注水体积下，配水池网络中的水位高度。关键在于如何高效地确定水位高度，使得所有水位以下的配水池能够容纳给定的水体积。以下是详细的解题步骤：

1. 输入处理：

   • 首先读取数据集的数量 k。
   • 对于每个数据集，读取配水池的数量 N。
   • 然后读取每个配水池的基底高度 b、高度 h、宽度 w 和深度 d，并计算每个配水池的底面积 s = w * d。

2. 二分查找水位高度：

   • 使用二分查找法来确定水位高度 mid，初始范围为 [0, INF]（INF 是一个足够大的数，比如 2,000,000）。
   • 对于每个中间值 mid，计算所有配水池中水位以下部分的体积总和 ans：
     • 如果水位 mid 高于配水池的顶部（即 mid >= b + h），则该配水池完全被填满，体积为 h * s。
     • 如果水位 mid 位于配水池的基底和顶部之间（即 b < mid < b + h），则计算水位以下部分的体积 (mid - b) * s。
     • 其他情况（水位低于基底），该配水池不贡献体积。
   • 比较 ans 和给定的水体积 V：
     • 如果 ans < V，说明水位需要升高，调整二分范围为 [mid, max]。
     • 否则，调整范围为 [min, mid]。

3. 输出结果：

   • 如果最终的水位 mid 达到 INF，说明水体积超过了所有配水池的总容量，输出 "OVERFLOW"。
   • 否则，输出水位高度，保留两位小数。

#include<stdio.h>
#include<string.h>
#define MAXD 50010
#define zero 1e-8
#define INF 2000000
struct cistern
{
    int b, h, s;
}c[MAXD];
int N;
double fabs(double x)
{
    return x < 0 ? -x : x;
}
int dcmp(double x)
{
    return fabs(x) < zero ? 0 : (x < 0 ? -1 : 1);
}
void init()
{
    int i, j, k, w, d;
    scanf("%d", &N);
    for(i = 0; i < N; i ++)
    {
        scanf("%d%d%d%d", &c[i].b, &c[i].h, &w, &d);
        c[i].s = w * d;
    }
}
void solve()
{
    int i, j, k;
    double max, min, mid, v, ans;
    scanf("%lf", &v);
    min = 0, max = INF;
    for(k = 0; k < 50; k ++)
    {
        mid = (max + min) / 2;
        ans = 0;
        for(i = 0; i < N; i ++)
        {
            if(dcmp(mid - c[i].b - c[i].h) >= 0)
                ans += c[i].h * c[i].s;
            else if(dcmp(mid - c[i].b) > 0)
                ans += (mid - c[i].b) * c[i].s;
        }
        if(dcmp(ans - v) < 0)
            min = mid;
        else
            max = mid;
    }
    if(dcmp(mid - INF) == 0)
        printf("OVERFLOW\n");
    else
        printf("%.2lf\n", mid);
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        init();
        solve();
    }
    return 0;
}