【题目链接】
http://poj.org/problem?id=3784
【算法】
对顶堆算法
要求动态维护中位数，我们可以将1-M/2（向下取整）小的数放在大根堆中，M/2+1-M小的数放在小根堆中
每次插入元素时，先将插入元素与小根堆堆顶比较，如果比堆顶小，则插入小根堆，否则，插入大根堆，然后，判断两个堆
的元素个数是否平衡，若不平衡，则交换两个堆的堆顶
【代码】
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 10010 int i,t,n,tmp,len,T;
int a[MAXN],ans[MAXN]; struct BHeap
{
int tot;
int hp[MAXN];
inline void clear()
{
tot = ;
}
inline void Up(int pos)
{
int fa;
if (pos == ) return;
fa = pos / ;
if (hp[pos] > hp[fa])
{
swap(hp[pos],hp[fa]);
Up(fa);
}
}
inline void Down(int pos)
{
int son;
son = pos * ;
if (son > tot) return;
if (son < tot && hp[son+] > hp[son]) son++;
if (hp[son] > hp[pos])
{
swap(hp[son],hp[pos]);
Down(son);
}
}
inline void Insert(int x)
{
tot++;
hp[tot] = x;
Up(tot);
}
inline void del()
{
swap(hp[],hp[tot]);
tot--;
Down();
}
inline int get()
{
return hp[];
}
} B;
struct SHeap
{
int tot;
int hp[MAXN];
inline void clear()
{
tot = ;
}
inline void Up(int pos)
{
int fa;
if (pos == ) return;
fa = pos / ;
if (hp[pos] < hp[fa])
{
swap(hp[pos],hp[fa]);
Up(fa);
}
}
inline void Down(int pos)
{
int son;
son = pos * ;
if (son > tot) return;
if (son < tot && hp[son+] < hp[son]) son++;
if (hp[son] < hp[pos])
{
swap(hp[son],hp[pos]);
Down(son);
}
}
inline void Insert(int x)
{
tot++;
hp[tot] = x;
Up(tot);
}
inline void del()
{
swap(hp[],hp[tot]);
tot--;
Down();
}
inline int get()
{
return hp[];
}
} S; int main()
{ scanf("%d",&T);
while (T--)
{
len = ;
scanf("%d%d",&t,&n);
S.clear(); B.clear();
for (i = ; i <= n; i++) scanf("%d",&a[i]);
for (i = ; i <= n; i++)
{
if (i == )
{
B.Insert(a[i]);
ans[++len] = a[i];
continue;
}
if (a[i] <= B.get()) B.Insert(a[i]);
else S.Insert(a[i]);
if (B.tot - S.tot >= )
{
tmp = B.get();
B.del();
S.Insert(tmp);
}
if (S.tot - B.tot > )
{
tmp = S.get();
S.del();
B.Insert(tmp);
}
if (i & ) ans[++len] = S.get();
}
printf("%d %d\n",t,len);
for (i = ; i <= len; i++)
{
if (i % == ) printf("%d",ans[i]);
else if (i % == ) printf(" %d\n",ans[i]);
else printf(" %d",ans[i]);
}
printf("\n");
} return ; }