题目描述

就不写了。偷懒

算法1

二分答案

从题目可知，数列是有序的，因此可以使用二分答案。
那么我们就可以套用二分答案的模板。模板一：找最小值；模板二：找最大值。
本题题目明确说“中位数能够尽可能大”。因此为模板二。
本题的坑在于 mid=(l+r)/2 这里。根据题目的数据范围 $a_i$ 最大值为 $10^9$，因此 l+r 可能超过了 int 范围，而不是 mid 超过了 int 范围。闫总坑到我了。所以数据需要使用 long long。
其他就没什么了，套模板二，想一下如何实现 check() 函数即可。

左端点

这个很自然，就是中位数

右端点

偷懒可以直接使用 $2*10^9$。
我们直接使用 $a[(n+1)/2]+K$ 即可。

check() 函数构造

将当前的中位数变成 mid，需要多少代价 $cnt$。将这个代价 $cnt$ 和 $K$ 进行比较。

时间复杂度

应该是O(N)。
因为读取数据使用O(N)，而二分查找只需要O(logK)。
合计为O(N+logK)。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+10;
ll a[MAXN];
int n, K;
//<= max
bool check(int mid) {
    //将中位数变成mid，需要操作多少次 
    int idx=(n+1)/2;//中位值
    int cnt=mid-a[idx];
    for (int i=idx+1; i<=n && a[i]<mid; i++) {
        cnt+=(mid-a[i]);
        if (cnt>K) {
            return false;
        }
    }
    return true;
}
ll bsearch(ll l, ll r) {
    ll mid;
    while (l<r) {
        mid=(l+r+1)/2;
        if (check(mid)) {
            l=mid;
        } else {
            r=mid-1;
        }
    }
    return l;
}
int main() {
    //freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);

    scanf("%d%d", &n, &K);
    for (int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a+1, a+n+1);

    //二分答案，因为有序 
    ll ans=bsearch(a[(n+1)/2], a[(n+1)/2]+K);
    printf("%lld\n", ans);

    return 0;
}