记录编号	228022	评测结果	EEEEEEEEEEEEEEEEEEEE
题目名称	中位数	最终得分	0
用户昵称	‎MistyEye	是否通过	未通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-02-19 06:23:40	内存使用	0.00 MiB

#include <cstdio>
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 =heap[a];
	heap[a] =heap[b];
	heap[b] =k;
}
inline void push(int x){
	heap[++size] =x;
	int pos =size,to;
	while(pos!=1){
		to =pos>>1;
		if(heap[to]<=heap[pos])return;
		swap(to,pos);
		pos =to;
	}						
}
inline int pop(){
	int ans =heap[1];
	heap[1] =heap[size--];
	int pos =1;
	while(pos<<1<=size){
		pos =pos<<1;
		if(pos|1<=size&&heap[pos]>heap[pos|1])
				pos++;
		if(heap[pos]>=heap[pos>>1])break;
		swap(pos,pos>>1);
	}
	return ans;
}
int main(){
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
	int N, a;
	N =read();
	for(int i=1; i<=(N>>1)+1; i++)
		a =read(),push(a);
	for(int i=(N>>1)+2; i<=N; i++){
		a =read();
		if(a>heap[1]){
			push(a);
			pop();
		}
	}
	if(N%2==1)printf("%.1lf", (double)pop());
	else{
		int x =pop();
		int y =pop();
		printf("%.1lf",  (x+y)/2.0);
	}
	return 0;
}