题解 P1627 【中位数】
诗乃
2016-11-14 18:47:22
搞个清新脱俗的算法
把中位数出现的位置设为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].
```cpp
#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);
}
```