题目重述

有 $n$ 个水桶排成一行，桶 $i$ 初始水量为 $v_i$，相邻桶 $i$ 和 $i+1$ 之间有一条位于高度 $h_i$ 的水平管道。
你可以向任意桶中投入粘土（每单位体积与水的体积相同），粘土沉底后会堵塞本桶与右侧桶之间的管道（当粘土高度 $\ge h_i$ 时）。
每次投粘土后，水会重新达到平衡（连通器原理）。
目标：最大化第一个桶最终的水量。

关键观察

$1$. 粘土只能堵住向右的管道（因为粘土沉在桶底，只影响本桶与右侧桶的连接）。 $2$. 一旦管道 $i$ 被堵住，左侧 $1 \dots i$ 与右侧 $i+1 \dots n$ 永久隔离，水无法再跨越。 $3$. 水总是从高水位向低水位流动，且只能通过水位 $\ge$ 管道高度的管道。 $4$. 初始状态是平衡的，即相邻桶的水位差不超过管道高度（否则水会流动直到平衡）。

问题转化

设最终第一个桶的水量为 $X$。
要检验 $X$ 是否可达，我们倒序扫描（从右向左）模拟“水能否从右边流到左边来满足 $X$”。

定义：

• $need$：桶 $1$ 还需要从右边获得多少水才能达到 $X$。
• 从桶 $n$ 到桶 $2$ 依次处理：
  • 如果桶 $i$ 的当前水量 $\ge X$，则它有多余的水可以向左传递，但前提是水位 $\ge h_{i-1}$（否则水无法通过管道 $i-1$）。
  • 如果桶 $i$ 的当前水量 $< X$，则它需要从右边吸水，这要求水位 $\ge h_{i-1}$（否则水无法流入），并且它自己无法提供多余的水给左边。

正确性解释

• 水只能从高水位流向低水位，且必须跨越管道 $i$ 时，水位必须 $\ge h_i$。
• 倒序扫描保证了当我们考虑桶 $i$ 时，右侧的水已经决定是否向左流，不会受左侧影响。
• 如果桶 $i$ 水量不足 $X$，它必须从右边吸水，那么它自身的水位必须 $\ge h_{i-1}$（否则水进不来），而且它没有多余的水给左边。
• 如果桶 $i$ 水量充足，它可以向左传递多余的水，但前提是水位 $\ge h_{i-1}$（否则水出不去）。
• 最终检查 $need$ 是否 $\le 0$，即桶$1$能否获得足够的水。

二分答案

由于 $X$ 越大越难满足，我们可以二分答案：

• 下界 $lo = 0$
• 上界 $hi = 1e12$（足够大，大于任何可能的水量）
• 每次取 $mid = (lo + hi) / 2$，调用 $can(mid)$。
• 若可行则 $lo = mid$，否则 $hi = mid$。
• 迭代 $80$ 次后，$lo$ 即为答案。

复杂度

• 每次 $can()$ 耗时 $O(n)$
• 二分 $O(\log(1e12)) \approx 40$ 次
• 总 $O(n \log M)$，$n \le 2\times 10^5$ 可行。

完整代码

#include <bits/stdc++.h>
using namespace std;

int n;
vector<double> v, h;

bool can(double target) {
    double need = max(0.0, target - v[0]); // 桶1还需要多少水
    for (int i = n - 1; i >= 1; --i) {
        if (v[i] >= target) {
            // 桶i的水量足够支撑 target，多余的水可以向左流
            double carry = v[i] - target;
            if (v[i] >= h[i - 1] - 1e-12) {
                // 水位高于管道，水可以向左流
                need = max(0.0, need - carry);
            }
            // 否则，水无法向左流，carry被浪费
        } else {
            // 桶i水量不足 target，它需要从右边吸水
            if (v[i] < h[i - 1] - 1e-12) {
                // 水位低于管道，水无法流入，失败
                return false;
            }
            // 否则，桶i的水位至少等于管道高度，水可以流入
            // 但桶i自己不足，它需要从右边吸水，need不受影响
        }
    }
    return need <= 1e-9;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    h.resize(n - 1);
    for (int i = 0; i < n - 1; ++i) cin >> h[i];

    double lo = 0, hi = 1e12;
    for (int iter = 0; iter < 80; ++iter) {
        double mid = (lo + hi) / 2;
        if (can(mid))
            lo = mid;
        else
            hi = mid;
    }
    cout << lo << "\n";

    return 0;
}

示例验证

样例 1

输入：

2
1 2
2

过程：

• 二分找到 $X=2.5$ 可行，$X=2.5+\epsilon$ 不可行。 输出：2.5 ✅

样例 2

输入：

3
3 0 0
6 9

输出：3.0 ✅

样例 3

输入：

5
10 0 0 0 5
11 1 2 5

输出：11.916666666666667 ✅

注意事项

• 使用 $double$ 浮点数，精度要求 $10^{-6}$，二分 $80$ 次足够。
• 比较时加上 $1e-12$ 容差，避免浮点误差。
• 初始状态平衡由输入保证，我们不需要额外检验。
• 上界 $1e12$ 足够大，因为最多所有水集中到桶$1$，总水量 $\le n \cdot 10^6 \le 2\times 10^{11}$，故安全。