2016"百度之星" - 初赛(Astar Round2B) 1006 中位数计数

时间:2023-03-09 09:47:39
2016"百度之星" - 初赛(Astar Round2B)  1006	中位数计数

思路:统计当前数左边比它小|大 i个人,相应右边就应该是比它大|小i个人

l数组表示左边i个人的方案

r表示右边i个人的方案

数组下标不可能是负数所以要加n

 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <algorithm>
#include <vector>
// #include<malloc.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const double pi = acos(-);
const LL MOD = 1e9+;
// const LL p = 1e9+7;
// inline int r(){
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
// return x*f;
// } int numm[],sum[],l[],r[];
int n,point,ans,b;
int a[]; int main() {
while(~scanf("%d",&n)) {
for(int i=; i<=n; i++) scanf("%d",&a[i]); for(int j=; j<=n; j++) {
b=a[j];
for(int i=;i<=n;i++) numm[i]=a[i];
// for(int i=0;i<=n;i++) l[i]=0;
// for(int i=0;i<=n;i++) r[i]=0;
// for(int i=0;i<=n;i++) sum[i]=0;
clc(l,);
clc(r,);
clc(sum,);
ans=;
for(int i=; i<=n; i++) {
if(numm[i]>b) numm[i]=;
else if(numm[i]==b) {
numm[i]=;
point=i;
} else numm[i]=-;
}
l[n]=;
r[n]=;
for(int i=point-; i>=; i--) {
sum[i]=sum[i+]+numm[i];
l[sum[i]+n]++;
}
for(int i=point+; i<=n; i++) {
sum[i]=sum[i-]+numm[i];
r[sum[i]+n]++;
}
for(int i=; i<=*n-; i++) ans+=l[i]*r[*n-i]; if(j==)
printf("%d",ans);
else
printf(" %d",ans);
}
printf("\n");
}
return ;
}