CF1486D Max Median

题目链接：CF1486D Max Median

题目描述

有一个长度为 n 的数组，找出 所有长度至少为 k 的子段 的 最大的中位数

如果一个数组 a 长度为 n ，且按照递增顺序排列。那么 \lfloor\frac{n+1}{2} \rfloor 位置上的数是这个数组的中位数。

Solution

自己想怎么也做不出来，看了题解才会

先是看了一个提示：How to solve the problem if all the values are −1 and 1? 。。然鹅还是不太会，但这个提示可以说是做法的核心了。

我们将问题转化，转化为验证答案是否能大于等于 x ，可以发现这个问题的答案是具有单调性的，那么就可以二分。

我们将序列中 小于 x 的数设置为 -1 ，大于等于 x 的值设置为 1 。

可以发现，如果一个子段的序列和为正数，那么这个子段的中位数一定是大于等于 x 的。

因为 \ge x 的数比 \le x 的数多，所以 \lfloor\frac{n+1}{2} \rfloor 这个位置上的数一定是 \ge x 的。

然后可以利用前缀和在 O(n) 的复杂度内算出子段最大和，检验它是否大于 1 即可。

复杂度 O(nlogn)

真是妙啊。。。问题 **中位数为 x ** 的答案不一定具有单调性，但是问题 **中位数是否大于等于 x ** 的答案就具有单调性。。然后转化了一下，验证也变的简单了。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,k;
int a[N];
pair<int,int> p[N];
int q[N];
int check(int x){
    int m=0;
    q[0]=0;
    for(int i=1;i<=k;++i) 
        if(a[i]<x) q[i]=q[i-1]-1;
        else q[i]=q[i-1]+1;
    if(q[k]>0) return 1;
    for(int i=k+1;i<=n;++i){
        if(a[i]<x) q[i]=q[i-1]-1;
        else q[i]=q[i-1]+1;
        m=std::min(m,q[i-k]);
        if(q[i]-m>0) return 1;
    }
    return 0;
}
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    int l=1,r=n<<3;
    while(l+1<r){
        int mid = l + r >>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%d",l);
}