← 返回题目列表

AtCoder · abc444_f

I. 一半和中位数

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

分数: 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.