一道二分题。
熟悉的 \(n \le 2 \times 10^5\)，一眼二分。
在 check(x) 函数里，我们需要判断的是在 \(k\) 次操作以内是否能将 \(x\) 变为中位数。显然的，我们只需要往上看，因为只有加法操作，将小的数进行操作一定不利。
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
ll n, k, ans;
ll a[200005], tmp[200005];
bool check(ll x) {
for (int i = 1; i <= n; i++) tmp[i] = a[i];
ll cnt = 0, mid = n / 2 + 1;
cnt += x - a[mid];
a[mid] = x;
for (int i = mid + 1; i <= n; i++) {
if (a[i] < a[i - 1]) {
cnt += a[i - 1] - a[i];
a[i] = a[i - 1];
}
}
for (int i = 1; i <= n; i++) a[i] = tmp[i];
if (cnt <= k) return 1;
return 0;
}
void f(ll l, ll r) {
while (l <= r) {
ll mid = (l + r) / 2;
if (check(mid)) {
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
}
signed main() {
ios :: sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
f(1, 2 * INF);
cout << ans;
return 0;
}