Ural 1306. Sequence Median

PRO IS HERE

优先队列；

维护一个大小为N/2的最大堆。

实现的话用STL 的 priority_queue

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<sstream>
#include<iostream>
using namespace std;

#define FOR(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define DOR(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define bug puts("Fuck");
#define LL long long
#define pb push_back
#define mp make_pair

#define nMax 250010
#define eps 1e-8
#define inf 0x7fffffff

int n;
priority_queue<unsigned int> que;
unsigned int a;


int main(){
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif
	while(~scanf("%d",&n)){
		int m = n/2 + (n%2==0?1:0);
		FOR(i,1,n) {
			scanf("%u",&a);
			que.push(a);
			if(que.size()>m) que.pop();
		}
		double ans=0.0;
		if(n%2==1)
			ans = que.top();
		else{
			ans += que.top();que.pop();ans+=que.top();
			ans /= 2.0;
		}
		printf("%.1lf\n",ans);
	}

	return 0;
}