贪心

$O(nlogn)$

C++ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200010;

typedef long long LL;

LL a[N], n, k;

// 由于中位数之前的数对结果没有影响, 故相当于把问题转换为
// 对中位数及后面一段数组进行增加操作, 使得最小的数最大

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    int r = n / 2 + 1;
    LL cnt = 1, x = a[n / 2];
    while(r < n && k > 0){
        if(r < n){
            if(a[r] == x) cnt++, r++;
            else{
                LL d = a[r] - x;
                if(cnt * d <= k){
                    k -= cnt * d;
                    x = a[r];
                    cnt++;
                    r++;
                    }
                else{
                    x += k / cnt;
                    k = 0;
                    break;
                    }
                }
            }
        }
    if(k > 0) x += k / cnt;
    cout << x << endl;
    return 0;
}