题目链接

http://poj.org/problem?id=3784

分析

动态维护序列中位数可用对顶堆实现，即用大根堆维护序列前一段，用小根堆维护序列后一段。

保证大根堆内元素均比小根堆内元素小，且两堆元素个数差不超过 $1$1。

每次输出时，元素个数较多的堆的堆顶元素即为当前序列中位数。

AC代码

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

inline int read() {
	int num = 0, flag = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flag = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		num = num * 10 + c - '0', c = getchar();
	return flag * num;
}

priority_queue<int> p;
priority_queue<int, vector<int>, greater<int> > q;

int main() {
	int t = read(), m;
	for (int i = 1; i <= t; ++i) {
		read(), m = read();
		printf("%d %d\n", i, m / 2 + 1);
		while (!p.empty()) p.pop();
		while (!q.empty()) q.pop();
		for (int j = 1; j <= m; ++j) {
			int x = read();
			if (p.empty() || x <= p.top()) p.push(x);
			else q.push(x);
			while ((int)(p.size() - q.size()) > 1) {
				q.push(p.top());
				p.pop();
			}
			while ((int)(q.size() - p.size()) > 1) {
				p.push(q.top());
				q.pop();
			}
			if (j & 1) {
				if (j != 1 && j % 20 == 1) puts("");
				printf("%d ", p.size() > q.size() ? p.top() : q.top());
			}
		}
		if (i != t) puts("");
	}
	return 0;
}