题目传送门
一道二分题……
熟悉的 n≤2×105,一眼二分。
在 check(x)
函数里,我们需要判断的是在 k 次操作以内是否能将 x 变为中位数。显然的,我们只需要往上看,因为只有加法操作,将小的数进行操作一定不利。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #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; }
|