#CF1201C. 最大化中位数

最大化中位数

CF1201C Maximum Median

题目描述

\hspace{15pt}给定一个长度为 nn 的数组 aa(nn 为奇数)。您可以对数组进行如下操作:

∙ \hspace{23pt}\bullet\,选择数组中的一个元素,使其增加 11。

\hspace{15pt}您至多可以进行 kk 次操作,请最大化数组的中位数。

\hspace{15pt}【名词解释】

∙ \hspace{23pt}\bullet\,中位数:中位数为将数组从小到大排序后,位于最中间位置的数。例如,[1,5,2,3,5][1,5,2,3,5] 的中位数是 33。

输入格式

\hspace{15pt}第一行输入两个整数 $n, k \left(1 \leqq n \leqq 2 \times 10^5;\ 1 \leqq k \leqq 10^9\right)$ 代表数组的长度和操作次数,其中 nn 为奇数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表数组 aa。

输出格式

\hspace{15pt}在一行上输出一个整数,代表经过至多 kk 次操作后数组的中位数的最大值。

测试样例

3 2
1 3 5
5

样例 1 解释

\hspace{15pt}对 a2a_2 进行两次操作,数组变为 [1,5,5][1,5,5],中位数为 55。

5 5
1 2 1 1 1
3

样例 2 解释

\hspace{15pt}一种最佳操作是使数组变为 [1,3,3,1,3][1,3,3,1,3],此时中位数为 33。

7 7
4 1 2 4 3 4 4
5

样例 3 解释

\hspace{15pt}一种最佳操作是使数组变为 [5,1,2,5,3,5,5][5,1,2,5,3,5,5],此时中位数为 55。