记录编号	228040	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	中位数	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	1.670 s
提交时间	2016-02-19 06:28:29	内存使用	1.00 MiB

#include <cstdio>
using namespace std;
int f,x;char ch;
inline int read(){
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int heap[250001], size =0;
inline void swap(int& a, int& b){int k =a;a =b;b =k;}
void push(int x){
	heap[++size] =x;
	int pos =size,to;
	while(pos!=1){
		to =pos/2;
		if( heap[to]<=heap[pos] ) return;
		swap(heap[to],heap[pos]);
		pos =to;
	}						
}
int pop(){
	int ans =heap[1];
	heap[1] =heap[size--];
	int pos =1;
	while(pos*2<=size){
		if(pos*2==size) pos=pos*2;
		else{
			if(heap[pos*2]>heap[pos*2+1])
				pos = pos*2+1;
			else pos = pos*2;
		}
		if(heap[pos]<heap[pos/2])
			swap(heap[pos],heap[pos/2]);
		else break;
	}
	return ans;
}
int main(){
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
	int N, a;
	N = read();
	int T = N/2 +1;
	for(int i=1; i<=T; i++){
		a = read();
		push(a);
	}
	for(int i=T+1;i<=N;i++){
		a = read();
		if( a>heap[1] ) pop(),push(a);
	}
	if(N%2==1) printf("%.1lf", (double)pop());
	else{
		int x =pop();
		int y =pop();
		printf("%.1lf",  (x+y)/2.0);
	}
	return 0;
}