算法

(贪心) $O(n)$

我们要求的是中位数，前一半的数可以直接舍去，只考虑后一半的数
现在就是要求第一个数能变成的最大值
如果第一个数能变成最后一个数那么所要消耗的k就是$sum=\sum_{i=0}^{m-2}b[m-1]-b[i]$
变成最后一个数字后$k-=sum$，现在所有数字都相同如果第一个数要增加，那么别的数也要增加，所以结果要加上k/m
如果加到了最后一个数k小于sum呢？
我们的代价从$sum=\sum_{i=0}^{m-2}b[m-1]-b[i]$变成了$sum=\sum_{i=0}^{m-3}b[m-2]-b[i]$
需要的sum减少了(i + 1) * (b[m-1]-b[m-2])，然后一直这样重复直到可以操作k次取得最大值

C++ 代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int n, k;
int a[N], b[N];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++ i) cin >> a[i];

    sort(a, a + n);
    int m = 0;
    for(int j = n / 2; j < n; ++ m, ++ j) b[m] = a[j];

    LL sum = 0;
    int maxv = b[0];
    for(int i = 0; i < m; ++ i) sum += b[m - 1] - b[i];

    if(sum <= k)
    {
        maxv = b[m - 1];
        k -= sum;
        printf("%d\n", maxv + k / m);
    }
    else
    {
        for(int i = m - 2; i >= 0; -- i)
        {
            sum -= (LL)(i + 1) * (b[i + 1] - b[i]);
            if(sum <= k)
            {
                printf("%d\n", b[i] + (k - sum) / (i + 1));
                break;
            }
        }
    }



    return 0;
}