F - 秋实大哥与妹纸

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 1500/1500KB (Java/Others)

Submit Status

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

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

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

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

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

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

Input

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

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

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

Output

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

Sample input and output

Sample Input	Sample Output
3 1 2 3	2.0

Hint

注意内存大小限制。

解题报告:

内存只能开一半..我们采用大根堆来维护，前一半直接读入大根堆，对于后一半的数据，若该数大于跟的max,则该元素是无用的，若小于，pop掉max值，再将该值压入heap中，最后根据n的奇偶性来读取heap前两层的数.

因为本题内存限制很紧。。因此使用的C语言来写

#include <stdio.h>

#define maxn 125005

int heapsize = ,heap[maxn],maxheapsize,n;

void swap(int *x,int *y)

{

   int temp = *x;

   *x = *y;

   *y = temp;

}

void insert(int x)

{

  heap[++heapsize] = x;

  int cur = heapsize , pre = heapsize / ;

  while(pre > )

   {

         if (heap[cur] > heap[pre])

          {

                swap(&heap[cur],&heap[pre]);

                cur = pre;

                pre = cur / ;

       }

      else

       break;

   }

}

void maintainheap()

{

   // New Ele insert,maintain the heap

   int cur =  , tar = *cur;

   while(tar <= maxheapsize)

    {

       if (tar +  <= heapsize && heap[tar+] > heap[tar])

        tar++;

       if (heap[tar] > heap[cur])

        {

            swap(&heap[tar],&heap[cur]);

            cur = tar;

            tar = cur*;

        }

       else

        break;

    }

}

int main(int argc,char *argv[])

{

  int i;

  scanf("%d",&n);

  maxheapsize = n/+;

  for(i =  ; i <= maxheapsize ; ++ i)

       {

          int temp;

          scanf("%d",&temp);

          insert(temp);

    }

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

    {

       int temp;

       scanf("%d",&temp);

       if (temp < heap[])

           {

             heap[] = temp;

             maintainheap();

        }

    }

  long long ans = ;

  if (n % )

   {

         ans = heap[];

         printf("%.1f\n",(double)ans);

   }

  else

   {

        ans = heap[];

        long long qans = heap[];

        if (heap[] > qans)

         qans = heap[];

        ans += qans;

        printf("%.1f\n",(double)ans/.*.);

   }

  return ;

}

巴特西

UESTC_秋实大哥与妹纸 2015 UESTC Training for Data Structures<Problem F>