← 返回题目列表

Codeforces · 2038/E

E. 桶

中文机器翻译题面 查看原题

假设您有 $$$n$$$ 个水桶排成一排,编号从 $$$1$$$ 到 $$$n$$$。

所有桶都是相等的,底部面积都等于一个单位,因此桶内水的体积等于水柱的高度。最初,第 $$$i$$$ 个桶有 $$$v_i$$$ 单位的水。

相邻的桶通过管道连接。换句话说,对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$i$$$,桶 $$$i$$$ 和 $$$i + 1$$$ 通过高度为 $$$h_i$$$ 的单个水平管道连接。管道的宽度可以忽略不计。这些管道允许水在桶之间流动。

现在你想玩桶。您的计划是通过将粘土扔进桶中来最大化第一个桶中的水量。在一步中,您可以选择任何一个桶并将一单位粘土投入其中。一单位粘土的体积与一单位水的体积相同。粘土比水重,不会与水混合,因此它会落到桶的底部,分布均匀。

粘土具有粘性结构,因此如果粘土柱足够高,它可以密封管道。更正式地说,假设管道的高度为 $$$h$$$。如果粘土柱的高度也是 $$$\boldsymbol{h}$$$ (或更低),则管道正在工作。但是,当您向桶中添加更多粘土时,管道会立即密封,从而防止水在桶之间流动。

您有一座粘土山,因此您可以多次重复上述步骤。然而,在这些步骤之间,您必须等到水达到新的平衡。

第一个桶最多可以收集多少水?

假设桶足够高,因此水不会溢出,并且管道宽度可以忽略不计。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 桶数。

第二行包含 $$$n$$$ 整数 $$$v_1, v_2, \dots, v_n$$$ ($$$0 \le v_i \le 10^6$$$),其中 $$$v_i$$$ 是第 $$$i$$$ 个桶中的初始水量。

第三行包含 $$$n - 1$$$ 整数 $$$h_1, h_2, \dots, h_{n - 1}$$$ ($$$1 \le h_i \le 10^6$$$),其中 $$$h_i$$$ 是第 $$$i$$$ 和第 $$$(i + 之间的管道高度1)$$$-st 桶。

输入的附加约束:给定的水高度处于平衡状态。

输出

打印一个数字——第一个桶中的最大水体积。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入 #1

2
1 2
2

输出 #1

2.500000000000000

输入 #2

3
3 0 0
6 9

输出 #2

3.000000000000000

输入 #3

5
10 0 0 0 5
11 1 2 5

输出 #3

11.916666666666667

注意

第一个示例的最优策略如下图所示: