中位数

中位数

时间： 1ms        内存：128M

描述：

    一个区间内的中位数定义为区间内所有值从小到大排序后排在正中间的那个数，如果值有偶数个，通常取最中间的两个数值的平均数作为中位数。
    现在有n个数，每个数都是独一无二的，求出每个数在多少个包含其的区间中是中位数（对于一个长度为n的数列，一共有n*(n+1)/2个区间）。

输入：

多组测试数据
第一行一个数n(n≤8000)
第二行n个数，0≤每个数≤10⁹

输出：

N个数，依次表示第i个数在多少包含其的区间中是中位数。

注意输出格式：两数之间用空格隔开，最后一个数后面没有空格。

示例输入：

5
1 2 3 4 5

示例输出：

1 2 3 2 1

提示：

参考答案（内存最优[1804]）：

#include <bits/stdc++.h>  
using namespace std;  
const int MAXN = 8007;  
int a[MAXN],cnt[MAXN<<1];  
int main()  
{  
    int n,ans;  
    while(scanf("%d",&n)!=EOF)  
    {  
        char s=' ';  
        for(int i=1; i<=n; ++i)  
            scanf("%d",&a[i]);  
        for(int i=1; i<=n; ++i)  
        {  
            memset(cnt,0,sizeof(cnt));  
            int poi=0;cnt[n]=1;  
            for(int j=i-1; j>0; --j)  
            {  
                if(a[j]<a[i])poi++;  
                else poi--;  
                cnt[poi+n]++;  
            }  
            poi=0;  
            ans=cnt[n];  
            for(int j=i+1; j<=n; ++j)  
            {  
                if(a[j]>a[i])poi++;  
                else poi--;  
                ans+=cnt[poi+n];  
            }  
            if(i==n)s='\n';  
            printf("%d%c",ans,s);  
        }  
    }  
    return 0;  
}  

参考答案（时间最优[468]）：

#include<bits/stdc++.h>
using namespace std;
const int M = 8005;
int a[8005], cnt[M << 1];
int main()
{
	int n, ant, ans;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
	{
		memset(cnt, 0, sizeof(cnt));
		ant = 0;
		cnt[M]++;
		for (int j = i - 1; j >= 1; j--)
		{
			if (a[i] > a[j])
				ant++;
			else
				ant--;
			cnt[M + ant]++;
		}
		ans = cnt[M];
		ant = 0;
		for (int j = i + 1; j <= n; j++)
		{
			if (a[i] < a[j])
				ant++;
			else
				ant--;
			ans += cnt[M + ant];
		}
		cout << ans;
		if (i != n)
			cout << " ";
		else
			cout << endl;
	}
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。