Codeforces Round 703 Div2 D

@(Codeforces Round ##703 Div2 D. Max Median 二分答案) 传送门：https://codeforces.com/contest/1486/problem/D

题意

给一个长度为n的数组，在里面找若干个长度$\ge k$的区间，问这些区间中最大的中位数是多少。 中位数，请输出最大值。

思路

依靠我们小学二年级的知识，将一个序列排序后，中位数为中间的数字。 奇数则为$\frac{(n+1)}{2}$，偶数为$\frac{n}{2}$处。 所以不管奇偶，都会有一半$(\ge)$中位数，一半$(<)$中位数。即$(\ge)$中位数$>(<)$中位数的数。

$eg:1\;2\;3 \;4。$ $3个(\ge)2，1个(<)2$，则$2$一定是中位数，$2个(\ge)3，2个(<)3$，则$3$不是中位数。

所以我们可以O(n)判断一个数字是不是中位数。

首先要获取这个中位数，也就是答案，那么就二分获取答案！

我们二分获取x之后，判断该数字是不是可以为中位数，如果是l=mid，否则r=mid-1。

对于怎么O(n)判断，用一个前缀和数字存取与x大小有关的。 $if(a[i]>=x) \;sum[i] = sum[i-1]+1$ $else\;sum[i]=sum[i-1]-1$

当处理完前缀和之后，从第k个开始检查，有没有在一个区间里起点到终点，$(\ge x)$的数是否大于$(<x)$。 存在，直接返回true，否则返回false。

Code（78MS）

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
##include "bits/stdc++.h"
using namespace std;

const int N = 2e5 + 10;
vector<int> a(N + 1), sum(N + 1);
int n, k;

bool check(int x) {
    for(int i = 1;i <= n; i++) sum[i] = sum[i - 1] + (a[i] >= x ? 1 : -1);
    int mx = 0, ans = sum[k];
    if(ans > 0) return 1;
    for(int i = k + 1;i <= n; i++) {
        mx = min(mx, sum[i - k]); // 终点
        ans = max(ans, sum[i] - mx); // 起点
        if(ans > 0) return 1;
    }
    return 0;
}

void solve() {
    cin >> n >> k;
    for(int i = 1;i <= n; i++) cin >> a[i];
    int l = 0, r = n + 1;
    while(l + 1 < r) {
        int mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << (check(l + 1) ? l + 1 : l) << endl;
}

signed main() {
    solve();
}