一个大根堆，一个小根堆。胡乱搞搞就可以了，根据中位数的计算方法。
#include<cstdio>
#include<iostream>
#include<algorithm>
struct Min_heap
{
int tail;
int data[100010];
int top()
{
return data[1];
}
void swap(int &a,int &b)
{
int c=a;
a=b;
b=c;
return ;
}
void insert(int value)
{
data[++tail]=value;
int pos=tail;
while(pos&&data[pos>>1]>data[pos])
{
swap(data[pos>>1],data[pos]);
pos>>=1;
}
return ;
}
void del()
{
swap(data[1],data[tail]);
tail--;
int pos=1,pass;
while(pos<=tail)
{
pass=pos;
if(data[pass]>data[pos<<1]&&(pos<<1)<=tail)
pass=pos<<1;
if(data[pass]>data[pos<<1|1]&&(pos<<1|1)<=tail)
pass=pos<<1|1;
if(pass==pos)
break;
swap(data[pass],data[pos]);
pos=pass;
}
return ;
}
};
struct Max_heap
{
int tail;
int data[100010];
int top()
{
return data[1];
}
void swap(int &a,int &b)
{
int c=a;
a=b;
b=c;
return ;
}
void insert(int value)
{
data[++tail]=value;
int pos=tail;
while(pos&&data[pos>>1]<data[pos]&&pos>>1)
{
swap(data[pos>>1],data[pos]);
pos>>=1;
}
return ;
}
void del()
{
swap(data[1],data[tail]);
tail--;
int pos=1,pass;
while(pos<=tail)
{
pass=pos;
if(data[pass]<data[pos<<1]&&(pos<<1)<=tail)
pass=pos<<1;
if(data[pass]<data[pos<<1|1]&&(pos<<1|1)<=tail)
pass=pos<<1|1;
if(pass==pos)
break;
swap(data[pass],data[pos]);
pos=pass;
}
return ;
}
};
Min_heap h1;
Max_heap h2;
int main()
{
int n;
scanf("%d",&n);
int a;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
/*h1.insert(a);
if(i%2)
{
h2.insert(h1.top());
h1.del();
printf("%d ",h2.top());
}*/
/*if(h1.top()>a)
h2.insert(a);
else*/
h1.insert(a);
if(h1.tail>h2.tail-1)
while(h1.tail>h2.tail-1)
{
h2.insert(h1.top());
h1.del();
}
if(h1.tail<h2.tail-1)
while(h1.tail<h2.tail-1)
{
h1.insert(h2.top());
h2.del();
}
if(i%2)
printf("%d
",h2.top());
}
return 0;
}