朝田诗乃 的博客

朝田诗乃 的博客

题解 P1627 【中位数】

posted on 2016-11-14 18:47:22 | under 题解 |

搞个清新脱俗的算法

把中位数出现的位置设为pos,比中位数大的设为1,小的设为-1.

lsum[i]表示i到pos的和,即1的个数和-1的个数差

rsum[i]表示pos到i的和,同理。

l[sum[i]]表示pos左边和为sum出现的次数

r[sum[i]]表示pos右边和为sum出现的次数

由于c++数组不能开负下标,所以需要向右偏移n

如果l[i]=r[-i]就可以将ans+=l[i]*r[-i].

#include <iostream>
#include <cstdio>
using namespace std;
int b,n,a[400001],pos,x,sum[200001],ans=0;
int l[400001],r[400001];
int main()
{
    //freopen("median.in","r",stdin);
    //freopen("median.out","w",stdout);
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x==b){pos=i;a[i]=0;}
        else
        if(x>b)a[i]=1;
        else a[i]=-1;
    }
    l[n]=1;r[n]=1;//l[0+n]=1;r[0+n]=1;0出现1次 
    for(int i=pos-1;i>=1;i--)
        {sum[i]=sum[i+1]+a[i];l[sum[i]+n]++;}
    for(int i=pos+1;i<=n;i++)
        {sum[i]=sum[i-1]+a[i];r[sum[i]+n]++;}
    for(int i=-n+n;i<=n-1+n;i++)
        ans+=l[i]*r[n-i+n];
    printf("%d",ans);
}