A16572 · Formation · GESP考级

题目描述

某天，“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 \times 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 \times 10^4$。 保证所有测试用例中 $q$ 的总和不超过 $5 \times 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