#CF1201C. 最大化中位数
最大化中位数
CF1201C Maximum Median
题目描述
给定一个长度为 的数组 ( 为奇数)。您可以对数组进行如下操作:
选择数组中的一个元素,使其增加 。
您至多可以进行 次操作,请最大化数组的中位数。
【名词解释】
中位数:中位数为将数组从小到大排序后,位于最中间位置的数。例如, 的中位数是 。
输入格式
第一行输入两个整数 $n, k \left(1 \leqq n \leqq 2 \times 10^5;\ 1 \leqq k \leqq 10^9\right)$ 代表数组的长度和操作次数,其中 为奇数。
第二行输入 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表数组 。
输出格式
在一行上输出一个整数,代表经过至多 次操作后数组的中位数的最大值。
测试样例
3 2
1 3 5
5
样例 1 解释
对 进行两次操作,数组变为 ,中位数为 。
5 5
1 2 1 1 1
3
样例 2 解释
一种最佳操作是使数组变为 ,此时中位数为 。
7 7
4 1 2 4 3 4 4
5
样例 3 解释
一种最佳操作是使数组变为 ,此时中位数为 。