Running Median 对顶堆 数据流中的中位数

链接：https://ac.nowcoder.com/acm/contest/1001/D
来源：牛客网

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.
输入描述:

The first line of input contains a single integer P(1≤P≤1000)P(1 \leq P \leq 1000)P(1≤P≤1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M(1≤M≤9999)M (1 \leq M \leq 9999)M(1≤M≤9999), giving the total number of signed integers to be processed. The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values.

输出描述:

For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output.



开始一个空序列,每次往序列里插入一个数字,奇数次插入的时候打印序列中的中位数,
经典老题了
两个堆来维护,

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#include <stdlib.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \
	do { \
		cout << "\033[31;1m " << #x << " -> "; \
		err(x); \
	} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
		inline void read(T &x, T2 &... oth) {
			x = 0;
			char ch = getchar();
			ll f = 1;
			while (!isdigit(ch)) {
				if (ch == '-') f *= -1; 
				ch = getchar();
			}
			while (isdigit(ch)) {
				x = x * 10 + ch - 48;
				ch = getchar();
			}
			x *= f;
			read(oth...);
		}
	template <typename T, typename... T2>
		inline void print(T x, T2... oth) {
			ll p3=-1;
			if(x<0) putchar('-'), x=-x;
			do{
				print_f[++p3] = x%10 + 48;
			} while(x/=10);
			while(p3>=0) putchar(print_f[p3--]);
			putchar(' ');
			print(oth...);
		}
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K, tot;


void PUSH(priority_queue<int>& lef, 
		priority_queue<int, vector<int>, greater<int> >& rig,
		int x) {
	tot ++;
	if(!rig.size() || x>rig.top()) 
		rig.push(x);
	else 
		lef.push(x);
	if(lef.size() > rig.size()+1) {
		rig.push(lef.top());
		lef.pop();
	}
	if(rig.size() > lef.size()+1) {
		lef.push(rig.top());
		rig.pop();
	}
}

#define QUERY (lef.size() > rig.size() ? lef.top() : rig.top())

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(Q);
	while(Q--) {
		read(m, n);
		printf("%d %d\n", m, n/2+1);
		priority_queue<int> lef;
		priority_queue<int, vector<int>, greater<int> > rig;

		int cnt = 0;
		for(int i=1, x; i<=n; i++) {
			read(x);
			tot = 0; //tot忘记清零 搞得内存超限
			PUSH(lef, rig, x);
			if(i & 1) {
				printf("%d", QUERY);
				++ cnt;
				if(cnt%10==0 || i==n) putchar('\n');
				else putchar(' ');
			}
//			printf("%d ", x);
		}
	}


#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}