FZU

洪尼玛有n个朋友,n个朋友排成一排,每个朋友都有一个自身的价值Ai,并且每个朋友自身的价值均不相同。现在每个朋友都能与他左右的若干个人组成一个区间,也可以他自己一个人组成一个区间。若这个区间的人数为奇数个,那么我们称其为“可行区间”。将一个 “可行区间”里所有朋友按价值排序后,中间的那个朋友就是这个“可行区间”里的“宝宝”。求每个朋友是多少个“可行区间”里的“宝宝”?

Input
多组测试数据。

输入第一行为正整数n,表示朋友个数。

接下来一行,有n个互不相同的正整数Ai,表示第i个朋友的价值。

n≤1000,Ai≤10^9

Output
输出n个正整数,依次表示第i个朋友是多少个“可行区间”里的“宝宝”。

Sample Input
5
1 2 3 4 5
Sample Output
1 2 3 2 1
Hint
例如3能组成的“可行间”有:{3},{1,2,3},{2,3,4},{3,4,5},{1,2,3,4,5} 共5个区间,其中在{3},{2,3,4},{1,2,3,4,5} 这3个“可行区间”里是宝宝。

分析:一开始以为什么主席树求第K大值或者线段树求中位数的高级操作,然而题目需要找的是中位数的所在不同区间的计数,连中位数都不用找,而是找一个数是中位数的区间。那么对于一个数,若在一个连续的区间内是中位数的话,那么这个区间中一定有一半的值大于这个数,另一半的值小于这个数。于是直接暴力找第i个数左边大于该数的个数。如果出现了小于该数的数,计数就减1,一大一小刚好抵消,当出现某个位置的计数等于0时,说明从位置i到这个位置,大于a[i]和小于a[i]的值的数量一样的,在此区间下a[i]为中位数,计数ans+1。

如果在i位置左边个数,和在位置i右边的个数通过互补能使得比a[i]大和比a[i]小的数一样多的话,也是要记入计数里的。这就需要我们对每个左边出现的计数情况都记录下来,当右边出现了刚好相反的计数时,互补得到0,在这样组合的情况下可以使该区间a[i]成为中位数。

#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=1e3+10;
int n,a[maxn],ans[maxn],has[maxn][maxn<<1];
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(has,0,sizeof has);
        memset(ans,0,sizeof ans);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            int cnt=0;
            for(int j=i-1; j>=0; j--)
            {
                if(a[j]>a[i])cnt++;
                else cnt--;
                if(!cnt) ans[i]++;
                has[i][cnt+maxn]++;
            }
        }
        for(int i=0; i<n; i++)
        {
            int cnt=0;
            for(int j=i+1; j<n; j++)
            {
                if(a[j]<a[i])cnt++;
                else cnt--;
                if(!cnt)ans[i]++;
                ans[i]+=has[i][maxn+cnt];
            }
        }
        for(int i=0; i<n; i++)
            printf("%d%c",ans[i]+1,i==n-1?'
':' ');
    }
}
原文地址:https://www.cnblogs.com/kuronekonano/p/11135749.html