Nowcoder 模拟赛 G1T1

2018-09-09 16:17:56


题意:给出一个序列,询问长度 $>=len$ 的子区间的中位数的最大值,偶数长度取中间靠前一个作为中位数


比赛的时候想到正解把自己hack了,交了个30分暴力

正解其实肥肠简单

二分一个数,检验ta是不是一个长度 $>=len$ 的区间的中位数即可

对于 $check$ ,把 $>=mid$ 的数记为 $1$ , $<mid$ 的数记为 $-1$

然后从 $1$ 到 $n$ 扫一遍

记录一个前缀最小值,当 $i>=len$ 的时候看一下这一段的和是否 $>0$ 就好了

所以考场上的每一个想法都要认真思考啊qwq,与正解擦肩而过太难受了

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5,inf=1e9;
int n,m,a[N],b[N],c[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline bool check(int k)
{
    for (reg int i=1;i<=n;i++) c[i]=(a[i]>=k?1:-1);
    for (reg int i=1,mi=inf;i<=n;i++)
    {
        if (i>=m) mi=min(mi,c[i-m]); c[i]+=c[i-1];
        if (i>=m&&c[i]-mi>0) return 1;
    }
    return 0;
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;i++) a[i]=b[i]=read();
    sort(b+1,b+n+1);
    int l=2,r=n-1,ans=0;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(b[mid])) ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",b[ans]);
    return 0;
}