CodeForces-1201C 题解

题目传送门

一道二分题……

熟悉的 n2×105n \le 2 \times 10^5,一眼二分。

check(x) 函数里,我们需要判断的是在 kk 次操作以内是否能将 xx 变为中位数。显然的,我们只需要往上看,因为只有加法操作,将小的数进行操作一定不利。

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;
}