51nod 1682 中位数计数

时间：2022-10-08 00:29:04

1682 中位数计数
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题

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

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

Input
第一行一个数n(n<=8000)

第二行n个数，0<=每个数<=10^9
Output
N个数，依次表示第i个数在多少包含其的区间中是中位数。
Input示例
5

1 2 3 4 5
Output示例
1 2 3 2 1
/*

51nod 1682 中位数计数

problem:

给你n个数,求出每个数在多少个包含其的区间中是中位数

solve:

如果a[i]在区间[l,r]是中位数,那么区间中大于a[i]和小于a[i]的数一样多. up[r]-up[l] == down[r]-down[l]

--> up[r]-down[r] == up[l]-down[l]. 就变成了当前i前面有多少个数up-down与其相等.

所以可以从中间往两边记录并统计.

hhh-2016/09/03-21:08:16

*/

#pragma comment(linker,"/STACK:124000000,124000000")

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <vector>

#include <math.h>

#include <queue>

#include <set>

#include <map>

#define lson  i<<1

#define rson  i<<1|1

#define ll long long

#define clr(a,b) memset(a,b,sizeof(a))

#define scanfi(a) scanf("%d",&a)

#define scanfs(a) scanf("%s",a)

#define scanfl(a) scanf("%I64d",&a)

#define scanfd(a) scanf("%lf",&a)

#define key_val ch[ch[root][1]][0]

#define eps 1e-7

#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

const ll mod = 1000000007;

const int maxn = 8080;

const double PI = acos(-1.0);

int n;

ll num[maxn*2];

int a[maxn];

ll cal(int id)

{

    int upcnt =0 ;

    int docnt = 0;

    memset(num,0,sizeof(num));

    num[8000] = 1;

    for(int i = id-1; i >= 1; i--)

    {

        if(a[i] > a[id]) upcnt++;

        if(a[i] < a[id]) docnt++;

        num[upcnt-docnt+8000] ++;

    }

    ll ans = 0;

    upcnt = docnt = 0;

    for(int i = id; i <= n; i++)

    {

        if(a[i] > a[id]) upcnt++;

        if(a[i] < a[id]) docnt++;

        ans += num[docnt-upcnt+8000];

    }

    return ans;

}

int main()

{

    while(scanfi(n) != EOF)

    {

        for(int i = 1; i<= n; i++)

            scanfi(a[i]);

        for(int i = 1; i<= n; i++)

        {

            printf("%I64d%c",cal(i),i == n ? '\n':' ' );

        }

    }

    return 0;

}

　　

相关文章