← 返回题目列表

Codeforces · 1201/C

C. 最大中位数

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$,其中 $$$n$$$ 是奇数。您可以用它进行以下操作:

- 选择数组的一个元素(例如 $$$a_i$$$)并将其增加 $$$1$$$(即将其替换为 $$$a_i + 1$$$)。

您希望使用最多 $$$k$$$ 操作使数组的中位数尽可能大。

奇数数组的中位数是数组按非降序排序后的中间元素。例如,数组 $$$[1, 5, 2, 3, 5]$$$ 的中位数是 $$$3$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$($$$1 \le n \le 2 \cdot 10^5$$$,$$$n$$$ 为奇数,$$$1 \le k \le 10^9$$$)— 数组中元素的数量以及可以进行的最大操作数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

输出

打印单个整数 - 运算后可能的最大中位数。

示例

输入 #1

3 2
1 3 5

输出 #1

5

输入 #2

5 5
1 2 1 1 1

输出 #2

3

输入 #3

7 7
4 1 2 4 3 4 4

输出 #3

5

注意

在第一个示例中,您可以将第二个元素增加两次。数组将是 $$$[1, 5, 5]$$$,它的中位数是 $$$5$$$。

在第二个示例中,最佳方案是增加第二个数字,然后增加第三个和第五个数字。这样答案就是$$$3$$$。

在第三个示例中,您可以进行四种操作:增加第一、第四、第六、第七元素。这样,数组将为 $$$[5, 1, 2, 5, 3, 5, 5]$$$,中位数将为 $$$5$$$。