CF1873E Building an Aquarium

你喜欢鱼，因此你决定建造一个水族箱。你有一块由 $n$ 列组成的珊瑚，第 $i$ 列的高度为 $a_i$ 单位。接下来，你将按照如下方式在珊瑚周围建造水箱： - 选择一个整数 $h \geq 1$，作为水箱的高度。在水箱的两侧建造高度为 $h$ 的墙。 - 然后，向水箱中注水，使得每一列的水面高度为 $h$，除非该列珊瑚的高度超过 $h$，此时该列不再加水。 例如，若 $a=[3,1,2,4,6,2,5]$ 且 $h=4$，你最终会用掉 $w=8$ 单位的水，如下图所示。  你最多可以用 $x$ 单位的水来填充水箱，但你希望建造尽可能高的水箱。你能选择的最大 $h$ 是多少？

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个正整数 $n$ 和 $x$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq x \leq 10^9$），分别表示珊瑚的列数和你最多能用的水量。 每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1 \leq a_i \leq 10^9$），表示每一列珊瑚的高度。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个正整数 $h$（$h \geq 1$），表示你能建造的最大水箱高度，使得填充水箱所需的水量不超过 $x$ 单位。 我们保证在这些约束下，总能找到这样的 $h$。

第一个测试用例如题面所示。若 $h=4$，需要 $8$ 单位的水，但若 $h$ 增加到 $5$，则需要 $13$ 单位的水，超过了 $x=9$。因此 $h=4$ 是最优的。 在第二个测试用例中，我们可以选择 $h=4$，每一列加 $3$ 单位水，总共用掉 $9$ 单位水。这是最优的。 在第三个测试用例中，我们可以选择 $h=2$，用完所有的水量，也是最优的。 由 ChatGPT 4.1 翻译