题目描述

你喜欢鱼，因此你决定建造一个水族箱。你有一块由 $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$。

样例

5
7 9
3 1 2 4 6 2 5
3 10
1 1 1
4 1
1 4 3 4
6 1984
2 6 5 9 1 8
1 1000000000
1

4
4
2
335
1000000001

样例说明

第一个测试用例如题面所示。若 $h=4$，需要 $8$ 单位的水，但若 $h$ 增加到 $5$，则需要 $13$ 单位的水，超过了 $x=9$。因此 $h=4$ 是最优的。

在第二个测试用例中，我们可以选择 $h=4$，每一列加 $3$ 单位水，总共用掉 $9$ 单位水。这是最优的。

在第三个测试用例中，我们可以选择 $h=2$，用完所有的水量，也是最优的。

由 ChatGPT 4.1 翻译

来源

Codeforces 1873E，英文题名 Building an Aquarium。