算法1

这里排序是O(n*log(n))， 然后后面的主循环最坏是O(k)，里面更新是O(n),但是只会更新一次，主要还是二分的，理论上是O(k * log(n)),但是不幸超时了。

(二分数组) $O(k * log(n))$

这里是我自己的一个思路，方法是对的。但是由于复杂度的原因超时了，暂时也记录一下。
首先整个题目需要排序，然后中位数就是正中间的数字。如果需要增加中位数的大小，那么就需要动态的增加后面的数字，并且在满足总操作数不大于k。因此这里每次将a[n - 1 >> 1] + 1与中位数后面的数字进行对比，找到最后一个小于或者等于该数字的数的下标。此时先判断k是否大于现在所需要的操作数，如果大于然则从中位数到这个数都加1，否则直接输出此时的中位数。

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int a[N], b[N];


int main()
{
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n);
    bool flag = false; //true表示k无法完成当前操作，并直接输出中位数。false表示可以完成当前操作
    if (n == 1) cout << a[0] + k << endl; //这里需要特判一下，因为n==1的时候
    else {
        while (k > 0)
        {
            int l = n - 1 >> 1, r = n - 1;
            while (l < r)
            {
                int mid = (LL)l + r + 1 >> 1;
                if (a[n - 1 >> 1] + 1 > a[mid]) l = mid;
                else r = mid - 1;
            } //找出最大的一个小于a[n - 1 >> 1] + 1的数字下标

            int t = r - (n - 1 >> 1) + 1; //总共需要操作的数量

            if (k < t)  //k无法支持完成操作，直接输出此时的中位数
            {
                cout << a[n - 1 >> 1] << endl;
                flag = true;
                break;
            }
            else //可以完成操作，更新数组并且更新K
            {
                k -= t;
                for (int i = n - 1 >> 1; i <= r; i ++) a[i] += 1;
            }
        }

        if(flag == false) cout << a[n - 1 >> 1] << endl;
    }
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(二分中位数) $O(n * log(k))$

这里换一个思路，直接考虑中位数的大小，肯定在0 到 2e9的范围内，不妨设为x，如果能够取到x则说明从中位数开始，所有的小于x的数在增加之后到了x所需要的操作数是不多余k的，明显x越大，所需要的操作数就越大，因此满足二分的性质

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

typedef long long LL;

int n, m;
int a[N];

bool inline check(int mid)
{
    LL res = 0;
    for (int i = n - 1 >> 1; i < n; i ++)
        if (mid > a[i]) res += mid - a[i]; //对于中位数后面的数，只要小于mid就需要补成mid
        else continue; //因为本来数列也是单调不减的，因为有一个不满足a[i] < mid,后面都会>= mid,因此直接continue
    return res <= m;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n);
    int l = 0, r = 2e9; //对0到2e9进行二分，因为中位数一定在这个区间内
    while (l < r)
    {
        int mid = (LL)l + r + 1 >> 1; //两个数相加可能爆int
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r << endl;

    return 0;
}