CF1201C - Maximum Median

思路

二分答案。对于一个mid，查询中位数要是为mid的话至少要做多少次操作，最小操作次数就是排序后从中位数开始计算max(0, mid - v[i])的和

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 5e5 + 10;


void solve() {
    i64 n, k;
    cin >> n >> k;
    std::vector<i64> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    sort(v.begin(), v.end());

    auto check = [&](int mid) {
        i64 res = 0;
        for (int i = (n + 1) / 2; i <= n; i++)
            res += max(0ll, mid - v[i]);
        return res > k;
    };

    i64 l = 1, r = 2e9;
    while (l < r) {
        i64 mid = (l + r + 1) / 2;
        if (check(mid)) r = mid - 1;
        else l = mid;

    }

    cout << l << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t --) solve();

    return 0;
}