题目:中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。

现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。


题解:一个数作为中位数,那么区间内大于他的数的数目以及小于他的数的数目必然相等。所有区间情况也就是三种:[_____i],[____i____],[i____]。其中第一种和第三种是一样的,而且也比较好计算,而第二种则需要组合一下了。我们假设左边大于当前数的数目为highl, 左边小于当前数的数目为lowl,同理,右边为,lowr, highr,如果当前数要作为中位数,那么则有:highl-lowl==highr-highl。

也可以参考一下freeloop的解答(中位数计数)。


代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=8005;
int data[maxn], ans[maxn], num[maxn*2];
int n;
inline int read(){
int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++){
        data[i]=read();
    }
    for(int i=1;i<=n;i++){
        memset(num, 0, sizeof(num));
        num[maxn]=1;    //单个区间
        int now=0;
        for(int j=i-1;j>=1;j--){
            if(data[j]>data[i])now++;
            else now--;
            num[maxn+now]++;
        }
        ans[i]=num[maxn];   //加上左边单侧的区间
        now=0;
        for(int j=i+1;j<=n;j++){
            if(data[j]<data[i])now++;
            else now--;
            ans[i]+=num[maxn+now];     //加上左右侧联合区间以及右侧单侧区间
        }
        printf("%d%c", ans[i], i==n?'\n':' ');
    }
    return 0;
}