思路
二分答案。对于一个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;
}