CF1201C · Maximum Median

• 难度：1400
• 标签：binary search、greedy、math、sortings
• 链接：https://codeforces.com/problemset/problem/1201/C
• 时间限制：2 seconds　内存限制：256 megabytes
• 出现位置：Day27-阶段模拟6-S T1T2稳分卷

中文题意

给定一个长度为 $n$（$n$ 为奇数）的整数数组 $a$。你可以进行如下操作：

• 选择数组中的一个元素（例如 $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

输出：

5

样例 2

输入：

5 5
1 2 1 1 1

输出：

3

样例 3

输入：

7 7
4 1 2 4 3 4 4

输出：

5