贪心 + 前缀和

时间复杂度 $O(n)$

分析：由于题目要求是不降序排序的中间值，那么我们把数组按升序排序后，把数组
分成前t个和后t + 1个数，我们发现对前t个数操作，不如对后t + 1个数操作优势大

证明

反证法：
假设对a[t]进行了k1次操作，a[t + 1]没有进操作
那么最优解就是 min(a[t] + k1, a[t + 2] + k3, ..., a[n] + kn)
这里我们发现，如果把k1次操作平移到后a[t + 1]上
a[t + 1] + k1 >= a[t] + k1
因此把a[t]换成a[t + 1]可以让中间值下界变大，与假设矛盾

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int a[N];
LL s[N];
LL d[N];
int n, k;

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

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];

    int t = n / 2 + 1;
    for (int i = t, j = 1; i <= n; i ++, j ++)
        d[i] = (LL)a[i] * j - (s[i] - s[t - 1]);

    LL res = 0;
    for (int i = t; i <= n; i ++)
    {
        if (k <= d[i])
        {
            res = ((s[i - 1] - s[t - 1]) + k) / (i - t);
            break;
        }
    }

    if (!res)
        res = (s[n] - s[t - 1] + k) / (n - t + 1);

    cout << res << endl;

    return 0;
}