URAL1306-Sequence Median（優先隊列）
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
input |
output |
4
3
6
4
5
4.5
Problem Source: II Collegiate Students Urals Programming Contest. Yekaterinburg, April 3-4, 1998
題意：求25000個數的中位數，但內存卡的很死，不能完全開下數組
思路：只要用優先隊列維護前二分之一加一大的數即可。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
priority_queue, greater > pq;
int main(){
int n;
while(~scanf("%d",&n)){
int cnt = n/2+1;
while(!pq.empty()) pq.pop();
for(int i = 0; i < n; i++){
int d;
cin >> d;
if(pq.size()
