poj3784Running Median——堆维护中间值

题目：http://poj.org/problem?id=3784

将较小的数放入大根堆，较大的数放入小根堆，控制较小数堆大小比较大数堆小1，则较大数堆堆顶即为中位数。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int p,bh,m,a[10005],hp1[10005],hp2[10005],ct1,ct2;
void pus1(int x)
{
ct1++;
hp1[ct1]=x;
int now=ct1;
while(now>1)
{
int tp=now/2;
if(hp1[now]>hp1[tp])
swap(hp1[now],hp1[tp]),now=tp;
else break;
}
}
void pus2(int x)
{
ct2++;
hp2[ct2]=x;
int now=ct2;
while(now>1)
{
int tp=now/2;
if(hp2[now]<hp2[tp])
swap(hp2[now],hp2[tp]),now=tp;
else break;
}
}
int del1()
{
int res=hp1[1];
swap(hp1[1],hp1[ct1]);
ct1--;
int now=1;
while(now*2<=ct1)
{
int tp=now*2;
if(tp<ct1&&hp1[tp]<hp1[tp+1])tp++;
if(hp1[now]<hp1[tp])
swap(hp1[now],hp1[tp]),now=tp;
else break;
}
return res;
}
int del2()
{
int res=hp2[1];
swap(hp2[1],hp2[ct2]);
ct2--;
int now=1;
while(now*2<=ct2)
{
int tp=now*2;
if(tp<ct2&&hp2[tp]>hp2[tp+1])tp++;
if(hp2[now]>hp2[tp])
swap(hp2[now],hp2[tp]),now=tp;
else break;
}
return res;
}
void mv1()
{
int k=del1();
pus2(k);
}
void mv2()
{
int k=del2();
pus1(k);
}
int main()
{
scanf("%d",&p);
while(p--)
{
scanf("%d%d",&bh,&m);
ct1=0;ct2=0;
memset(hp1,0,sizeof hp1);
memset(hp2,0,sizeof hp2);
int js=0;
for(int i=1;i<=m;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
if(a[i]<hp1[1])
pus1(a[i]);
else pus2(a[i]);
if(i%2)
{
while(ct1>ct2-1)mv1();
while(ct1<ct2-1)mv2();
js++;
if(js==1)printf("%d %dn",bh,(m+1)/2);
printf("%d ",hp2[1]);
if(js%10==0)printf("n");
}
}
if(js%10)printf("n");
}
return 0;
}