题解 P1627 【中位数】

诗乃

2016-11-14 18:47:22

Solution

搞个清新脱俗的算法 把中位数出现的位置设为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); } ```