牛客 172A 中位数 题解【二分答案】【前缀和】

作者: wjyyy 分类: 二分,解题报告 发布时间: 2018-09-09 16:34

点击量:31

 

    排序后的区间第K大问题??

 

题目描述

小N得到了一个非常神奇的序列\(A\)。这个序列长度为\(N\),下标从\(1\)开始。\(A\)的一个子区间对应一个序列,可以由数对\([l,r]\)表示,代表\(A[l],A[l+1],\dots ,A[r]\)这段数。对于一个序列\(B[1],B[2],\dots ,B[k]\),定义\(B\)的中位数如下:
1. 先对\(B\)排序。得到新的序列\(C\)。
2. 假如\(k\)是奇数,那么中位数为\(C[\frac{k+1}2]\)。假如\(k\)为偶数,中位数为\(C[\frac k2]\)。
对于\(A\)的所有的子区间,小N可以知道它们对应的中位数。现在小N想知道,所有长度\(\ge Len\)的子区间中,中位数最大可以是多少。
 

输入描述:

第一行输入两个数\(N,Len\)。

第二行输入序列\(A\),第\(i\)个数代表\(A[i]\)。

输出描述:

一行一个整数,代表所有长度\(\ge Len\)的子区间中,最大的中位数。

 

输入输出样例:

输入样例:

11 3
4864 8684 9511 8557 1122 1234 953 9819 101 1137 1759 

输出样例:

8684

说明

数据范围:
\(30\%: n\le 200\),
\(60\%: n\le 2000\),
另外有\(20\%\):不超过\(50\)个不同的数,
\(100\%:1\le Len\le n\le 10^5, 1\le a[i]\le 10^9\)

 

题解:

    [Tjoi2016&Heoi2016]排序的思路很像。都是二分答案;将大的设成1,小的设成0。而这个题特殊就在于它设置的比这个数小是-1。

 

    先看暴力,首先这个题是要求所有区间的中位数,区间有\(n^2\)个,每次求中位数是\(n\log n\),总复杂度是\(O(n^3\log n)\)。枚举左端点后可以用平衡树来维护区间的中位数。时间复杂度\(O(n^2\log n)\)。

 

    而我们要求最大的中位数,这个答案是具有单调性的,因为如果\(x\)不能作为中位数,那么对于\(\forall y\ge x\)都不能作为中位数,因此考虑二分答案。但是二分答案了就要有一个检验的标准,如何检验\(x\)是否能作为中位数呢?中位数就是在区间\([l,r]\)中排第\(\lfloor\frac{r-l+2}2\rfloor\)小的那个数,因此我们只需要判断\(x\)能不能作为一个区间的第(区间长度+1)/2小即可,那么区间中就有不大于(区间长度-1)/2个比它小的数,那么在检验它时就把大于等于它的数置1,小于等于它的数置-1。如果发现有一段长度不小于len的区间,权值和为正,说明这个数小于等于中位数。如果没有找到,就说明这个数一定大于中位数。

    这个图就是简单的流程,答案为6。不过我们看到图中出现了“前缀和”数组,这个是用来找有没有大于0的区间用的,每次更新答案,比较距离在当前点左边\(len\)长度位置的前缀和。维护这些合法区间(即当前位置\(-len\)处以左)中的最小前缀和,判断当前前缀和减去它是否为正即可。也就是在维护区间和\(sum[r]-sum[l-1]\)最大,我们无法决定\(sum[r]\),因为\(r\)是确定的,但是\(l\)的取值有很多,维护那个最小的\(sum[l-1]\),就可以让\(sum[r]-sum[l-1]\)最大。如果无论如何也没有为正的区间,二分答案返回false。这个处理类似POJ 2018 Best Cow Fences,比较经典。

 

Code:

#include<cstdio>
#include<cstring>
int a[100100];
int sum[100100];
int n,m;
bool check(int x)
{
    sum[0]=0;
    for(int i=1;i<=n;++i)
        if(a[i]>=x)
            sum[i]=sum[i-1]+1;
        else
            sum[i]=sum[i-1]-1;
    int mn=sum[1];
    if(sum[m]>0)
        return true;
    for(int i=m+1;i<=n;++i)
    {
        if(sum[i]-mn>0)
            return true;
        mn=mn<sum[i-m+1]?mn:sum[i-m+1];
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    int l=1,r=1000000001,mid;
    while(l<r)
    {
        mid=l+r>>1;
        if(check(mid))
            l=mid+1;
        else
            r=mid;
    }
    printf("%d\n",l-1);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */