CF1486 D.Max Median【二分】

题目链接：codeforces 1486D

题解

二分中位数，每次将大于等于 mid 的数标记为 ，否则标记为 。

我们要找到一个长度为 k 的区间，枚举右端点，每次只要找到一个左端点，使区间 的和大于 （因为中位数是向下取整，故不能取到等号），用前缀和维护即可。

因为是在区间 寻找左端点，且区间是连续的，故维护最小的前缀和，只要这个区间和大于 满足条件即可。

参考代码

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
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, k;
int a[N];
int b[N]; // 标记数组
int pre[N]; // 记录前i个前缀和
int mn[N]; // 记录前i个最小的前缀和
void init() {for (int i = 1; i <= n; i++) b[i] = pre[i] = 0, mn[i] = 0x3f3f3f3f;}
bool check(int x) {
    init();
    for (int i = 1; i <= n; i++) {
        if (a[i] >= x) b[i] = 1;
        else b[i] = -1;
    }
    for (int i = 1; i <= n; i++) pre[i] = pre[i-1] + b[i];
    for (int i = 1; i <= n; i++) mn[i] = min(mn[i-1], pre[i]);
    for (int i = k; i <= n; i++) { // 枚举右端点
        int sum = pre[i] - mn[i-k]; // 贪心思想
        if (sum > 0) return true;
    }
    return false;
}
int main() {
   cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = n, mid;
    while (l < r) {
        mid = (l+r+1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << l << endl;
    return 0;
}