CDOJ 1063 堆排序模板

D - 秋实大哥与妹纸

Time Limit:1000MS Memory Limit:1500KB 64bit IO Format:%lld & %llu

Submit Status Practice UESTC 1063

Appoint description:
System Crawler (2016-04-26)

Description

致中和，天地位焉，万物育焉。秋实大哥是一个追求中庸的人。

虽然秋实大哥的仰慕者众多，但秋实大哥不喜欢极端的妹纸。所以他想从所有仰慕自己的妹纸中挑选出一个符合中庸之道的。

每一个妹纸对秋实大哥的仰慕程度可以用一个整数ai来表示，秋实大哥想要找出这些数的中位数。

计算有限个数的数据的中位数的方法是：

把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；

如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。

Input

第一行有一个整数n，表示秋实大哥的仰慕者数目。

接下来n行，每行有一个正整数ai。

1≤n≤250000，1≤ai<231。

Output

输出这n个数的中位数，保留一位小数。

Sample Input

3
1
2

Sample Output

2.0

Hint

注意内存大小限制。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long LL;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int maxn=125000;

int hp[maxn+10],sz;

void push(int x)

{

     sz++;

     int pre=sz/2,cur=sz;

     while(pre>0)

     {

        if(hp[pre]<=x) break;

        hp[cur]=hp[pre];

        cur=pre;

        pre=pre/2;

     }

     hp[cur]=x;

}

void down(int i)

{

    int x=hp[i];

    int pre=i,chi=2*i;

    while(chi<=sz)

    {

        chi+=((hp[chi]>hp[chi+1])&&(chi+1<=sz));

        if(hp[chi]>=x) break;//注意是和x比啊，假设x放在父节点进行检验

        hp[pre]=hp[chi];

        pre=chi;

        chi*=2;

    }

    hp[pre]=x;

}

void change(int x)

{

    if(x<hp[1]) return;

    hp[1]=x;

    down(1);

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        MM(hp,inf);//维护一个最小堆

        int x;

        sz=0;

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

        {

            scanf("%d",&x);

            push(x);

        }//5个的话读入3个，6个的话读入4个

        for(int i=n/2+2;i<=n;i++)

        {

            scanf("%d",&x);

            change(x);

        }

        if(n%2==1)

            printf("%.1f\n",(double)hp[1]);

        else

            {

                double minn=min(hp[2],hp[3]);//没有限定左右儿子的大小

                printf("%.1f\n",((hp[1]+minn)/2.0));//可能爆int

            }

    }

    return 0;

}

巴特西

CDOJ 1063 堆排序模板

最新文章

热门文章