← 返回题目列表

Codeforces · 1873/E

E. 建造一个水族馆

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

你喜欢鱼,这就是你决定建造一个水族馆的原因。您有一块由 $$$n$$$ 柱组成的珊瑚,其中第 $$$i$$$ 的高度为 $$$a_i$$$ 个单位。然后,您将在珊瑚周围建造一个水箱,如下所示:

- 选择一个整数 $$$h \geq 1$$$ — 水箱的高度。在水箱两侧建造高度 $$$h$$$ 的墙。
- 然后,将水箱注满水,使每根柱子的高度为$$$h$$$,除非珊瑚高于$$$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$$$ 这样的值总是存在。

示例

输入 #1

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

输出 #1

4
4
2
335
1000000001

注意

第一个测试用例如声明中所示。当 $$$h=4$$$ 时,我们需要 $$$8$$$ 单位的水,但如果 $$$h$$$ 增加到 $$$5$$$,我们需要 $$$13$$$ 单位的水,这比 $$$x=9$$$ 多。所以 $$$h=4$$$ 是最优的。

在第二个测试用例中,我们可以选择 $$$h=4$$$ 并向每列添加 $$$3$$$ 单位,总共使用 $$$9$$$ 单位的水。可以证明这是最优的。

在第三个测试用例中,我们可以选择 $$$h=2$$$ 并使用所有的水,因此这是最佳的。