1201C. C. Maximum Median

CF1201C. Maximum Median

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

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

• 选择数组中的一个元素，使其增加 $1$。

您有 $k$ 次操作机会，请最大化数组的中位数。

一组数据的中位数是指数组从小到大排序后位于最中间的数，例如 $[1,5,2,3,5]$ 的中位数是 $3$。

输入格式

第一行两个整数 $n$ （$1 \leq n \le 2\times 10^5$）和 $k$（$1 \leq k \leq 10^9$）。
第二行一共 $n$ 个整数，表示数组 $a$（$1 \leq a_i \leq 10^9$）。

输出格式

一个整数，经过 $k$ 次操作后数组最大中位数

样例输入 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$ 中，对 $a_2$ 进行两次操作，数组变为 $[1,5,5]$；

样例 $2$ 中，一种最佳操作是使数组变为 $[1,3,3,1,3]$；

样例 $3$ 中，一种最佳操作是使数组变为 $[5,1,2,5,3,5,5]$。