← 返回题目列表

Codeforces · 2057/F

F. 编队

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

有一天,“T一代”的老师们决定给学生们灌输纪律,于是他们把他们排成一排,让他们按顺序计算。共有 $$$n$$$ 个学生,队列中第 $$$i$$$ 个学生的身高为 $$$a_i$$$。

如果对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$i$$$,以下条件成立:$$$a_i \cdot 2 \ge a_{i + 1}$$$,则该线是舒适的。最初,线路很舒服。

老师们不喜欢队伍的最大高度太小,所以他们想给学生喂披萨。您知道,当学生吃一个披萨时,他们的身高会增加 $$$1$$$。一份披萨只能由一名学生吃,但每个学生可以吃无限数量的披萨。重要的是,在所有学生都吃完披萨后,排队的时间要舒适。

老师们对于要订购多少个披萨有 $$$q$$$ 选项。对于每个选项 $$$k_i$$$,回答问题:如果学生最多吃 $$$k_i$$$ 披萨,则可以达到的最大高度 $$$\max(a_1, a_2, \ldots, a_n)$$$ 是多少。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每组测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^4$$$) - 学生数量和老师将订购多少个披萨的选项数量。

每组测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 学生的身高。保证一开始,该线是舒适的。

每组输入数据的以下每一行 $$$q$$$ 都包含一个整数 $$$k_i$$$ ($$$1 \le k_i \le 10^9$$$) - 学生可以吃多少个披萨的下一个限制。

保证所有输入数据集的 $$$n$$$ 值的总和不超过 $$$5 \cdot 10^4$$$。

保证所有输入数据集的 $$$q$$$ 值的总和不超过 $$$5 \cdot 10^4$$$。

输出

对于每个测试用例,对于学生可以吃多少个披萨的每个限制,输出在确保线路舒适的情况下可以达到的最大值 $$$\max(a_1, a_2, \ldots, a_n)$$$。

示例

输入 #1

3
2 1
10 20
10
6 7
3 1 2 4 5 6
1
2
4
8
16
32
64
10 4
1 2 4 8 16 32 64 128 256 512
10
100
1000
10000

输出 #1

26
7 8 10 12 19 35 67
513 560 1011 10001

注意

在第一组输入数据的第一个查询中,可以先给第一个学生$$$3$$$披萨,然后给第二个学生$$$6$$$披萨,得到最终的数组$$$[13, 26]$$$(这条线很舒服,因为$$$13 \cdot 2 \ge 26$$$),其中最大元素为$$$26$$$。