分数: 550 点
问题陈述
有 N 棒,以及长度 i- 第根棍子是 A_i.
您将执行以下操作 M 次:
- 至少选择一根长度的棍子 2,让 l 是这根棍子的长度。将这根棍子分成两根长度相同的棍子 \left\lfloor\frac{l}{2}\right\rfloor 和 \left\lceil\frac{l}{2}\right\rceil.
从约束条件可以证明可以执行该操作 M 次。
之后 M 操作, N+M 棍棒将保留。找出这些木棍长度中位数的最大可能值。
解决 T 每个输入的测试用例。
中位数是多少?
当 N 是偶数,中位数 N+1 数字是 (1+\frac{N}{2})- 按升序排序时的第一个值。例如,中位数 (1,3,4,5,8) is 4,以及中位数 (2,2,2) is 2.
请注意,在这个问题中,从约束来看,长度中位数要考虑的木棍数量始终是奇数。
约束
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq M \leq \sum_{i=1}^{N}{A_i} - N
- N+M 是奇数。
- 总和 N 所有测试用例最多 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例均按以下格式给出:
N M A_1 A_2 \ldots A_N
输出
输出答案 总共 T 行。 的 t- 第行应包含以下问题的答案 t- 第一个测试用例。
示例输入 1
3 5 2 14 2 5 19 1 10 1 10 6 7 6 2 20 9 16 3 3 4 1 444 444 44 444
示例输出 1
7 7 444
在第一个测试用例中,如果你选择长度的棍子 14 第一次操作时,被分成两根长度的棒 7,现在你有六根长度的棍子 7,7,2,5,19,1。 如果你选择长度的棍子 19 在第二次操作中,被分成两根长度的棒 9,10,现在你有七根长度的棍子 7,7,2,5,9,10,1。 在这种情况下,棒长度的中位数是 7.