HDU 5701 ——中位数计数——————【思维题】

中位数计数

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 764    Accepted Submission(s): 309

Problem Description

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

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

Input

多组测试数据

第一行一个数n(n≤8000)

第二行n个数，0≤每个数≤109,

Output

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

Sample Input

5
1 2 3 4 5

Sample Output

1 2 3 2 1

Source

2016"百度之星" - 初赛（Astar Round2B）

解题思路：参考：http://blog.csdn.net/jtjy568805874/article/details/51477656 思路真的很巧妙。

暴力枚举每个数a[i]，然后枚举前面j位置，记录a[j]到a[i]之间a[j]比a[i]小或大的数的个数，然后枚举后面j的位置，累计a[i]到a[j]之间的a[j]比a[i]大或小的数的个数。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<string>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
#pragma comment(linker, "/STACK:102400000,102400000")
const int maxn = 1e5+300;
const int INF = 0x3f3f3f3f;
typedef long long  LL;
typedef unsigned long long ULL;
int a[maxn], cnt[maxn];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i = 1; i <= n; i++){
            scanf("%d",&a[i]);
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= 2*n; j++){
                cnt[j] = 0;
            }
            cnt[n] = 1;
            int x = 0;
            for(int j = i-1; j >= 1; j--){
                if(a[j] < a[i]){
                    x--;
                }else{
                    x++;
                }
                cnt[n+x]++;
            }
            int ans = cnt[n];
            x = 0;
            for(int j = i+1; j <= n; j++){
                if(a[j] > a[i]){
                    x--;
                }else{
                    x++;
                }
                ans += cnt[n+x];
            }
            printf("%d",ans);
            printf("%c",i == n ? '\n' : ' ');
        }
    }
    return 0;
}