首页 > 代码库 > URAL 1306-Sequence Median(堆)

URAL 1306-Sequence Median(堆)

2024-07-28 00:55:50   222人阅读

1306. Sequence Median

Time limit: 1.0 second
Memory limit: 1 MB
Language limit: C, C++, Pascal
Given a sequence of N nonnegative integers. Let‘s define the median of such sequence. If N is odd the median is the element with stands in the middle of the sequence after it is sorted. One may notice that in this case the median has position (N+1)/2 in sorted sequence if sequence elements are numbered starting with 1. If N is even then the median is the semi-sum of the two "middle" elements of sorted sequence. I.e. semi-sum of the elements in positions N/2 and (N/2)+1 of sorted sequence. But original sequence might be unsorted.
Your task is to write program to find the median of given sequence.

Input

The first line of input contains the only integer number N — the length of the sequence. Sequence itself follows in subsequent lines, one number in a line. The length of the sequence lies in the range from 1 to 250000. Each element of the sequence is a positive integer not greater than 231?1 inclusive.

Output

You should print the value of the median with exactly one digit after decimal point.

Sample

inputoutput
4
3
6
4
5

4.5

题目很简单，就是求一个序列的中位数，如果这个序列的长度为偶数，输出中间的两个的平均数，但内存卡的很紧，所以不能排序暴力，可以建一个最大堆维护序列前n/2+1个元素，这样内存最多用n/2+1。优先队列900多k，换成数组堆后600k+。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=250000;
int a[maxn/2+10];
int main()
{
    int n;double ans;
    while(scanf("%d",&n)!=EOF)
    {
       int num=0,x;
       for(int i=0;i<n/2+1;i++)
       scanf("%d",&a[i]);
       make_heap(a,a+n/2+1);
       for(int i=n/2+1;i<n;i++)
       {
           scanf("%d",&x);
           if(x<a[0])
           {
               pop_heap(a,a+n/2+1);
               a[n/2]=x;
               push_heap(a,a+n/2+1);
           }
       }
       if(n%2)
       {
		   ans=(double)a[0];
		   printf("%.1lf\n",ans);
       }
       else
       {
           ans=(double)a[0];
           pop_heap(a,a+n/2+1);
           ans+=(double)a[0];
		   printf("%.1lf\n",ans/2.0);
       }

    }
    return 0;
}



URAL 1306-Sequence Median(堆)


联系
我们