记录编号	228205	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	中位数	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.769 s
提交时间	2016-02-19 09:15:32	内存使用	0.75 MiB

#include<cstdio>
#define lch(x) (x<<1)+1
#define rch(x) (x<<1)+2
#define prt(x) (x-1)>>1
int heap[250005];//小顶堆 
int len = 0;
inline int swap(const int &a,const int &b){
	heap[a]^=heap[b]^=heap[a]^=heap[b];
	return b;
}
inline void add(int &a){
	heap[len++]=a;
	int p = len-1;
	while(p&&heap[prt(p)]>heap[p])p=swap(p,prt(p));
}
void del(){
	heap[0]=heap[--len];
	int p = 0;
	while(rch(p)<len){
		if(heap[lch(p)]<heap[p]&&heap[rch(p)]<heap[p]){
			if(heap[lch(p)]<heap[rch(p)])p=swap(p,lch(p));
			else p=swap(p,rch(p));
		}else if(heap[lch(p)]<heap[p])p=swap(p,lch(p));
		else if(heap[rch(p)]<heap[p])p=swap(p,rch(p));
		else break;
	}
	if(rch(p)==len&&heap[lch(p)]<heap[p])p=swap(p,lch(p));
}
int read(){
	int x;char ch;bool minus=false;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if(ch=='-'){
		ch=getchar();
		minus=true;
	}
	x=ch-48;
	while(ch=getchar(),ch<='9'&&ch>='0')x=x*10+ch-48;
	if(minus)x=-x;
	return x;
}
int main(){
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
	int n;n=read();
	int lim = (n>>1);int tmp,a;
	for(int i=0;i<n;++i){
		tmp=read();
		if(i>lim){
			if(heap[0]<tmp){
				add(tmp);del();
			}
		}
		else add(tmp); 
	}
	if(n&1)printf("%.1lf",double(heap[0]));
	else{
		a=heap[0];del();tmp=heap[0];
		printf("%.1lf",(tmp+a)/2.0);
	} 
	fclose(stdin);fclose(stdout);
	return 0;
}