POJ 3784 Running Median【对顶堆】

传送门
题目大致意思：依次读入一个整数序列，每当读入的整数个数为奇数时，输出已经读入的整数构成的序列的中位数
手写的二叉堆只过了例样，调了半天还是WA
无奈只能投机取巧用stl的优先队列

思路：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main(){
	int T;
	cin>>T;
	while (T--) {
		int Case, M;
		cin >> Case >> M;
		printf("%d %d\n",Case,M&1?(M+1)/2:M/2);
		priority_queue<int> q1;//大根堆 
		priority_queue<int,vector<int>, greater<int> > q2; //小根堆 
		for (int i = 1;i <= M;i++){
				int x;cin>>x;
			    if(q2.empty()||x<=q2.top()) q1.push(x);
    			else q2.push(x);
    			if(q1.size() > q2.size() + 1) { q2.push(q1.top()); q1.pop(); }
    			if(q2.size() > q1.size() ) { q1.push(q2.top()); q2.pop(); }
    			if(i&1){
    				 printf("%d%c",q1.top(),i==M?'\n':' ');
                	 if(i%20==19)printf("\n");
				}
			}
	}
}

还有我发现大根堆，小根堆可以互相逻辑表示。
例如 1 2 3 4 5
在大顶堆依次弹出出为 5 4 3 2 1
如果把例子前置一个负号，放入大根堆 ：（-1），（-2），（-3），（-4），（-5）
弹出后在把他们变回来 就相当于小根堆的弹出 1 2 3 4 5
下面的用一种优先队列表示大根堆，和小根堆的AC的代码：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main(){
	int T;
	cin>>T;
	while (T--) {
		int Case, M;
		cin >> Case >> M;
		printf("%d %d\n",Case,M&1?(M+1)/2:M/2);
		priority_queue<int,vector<int>, greater<int> > q1,q2; //小根堆  大根堆 
		for (int i = 1;i <= M;i++){
				int x;cin>>x;
			    if(q2.empty()||x<=-q2.top()) q2.push(-x);
    			else q1.push(x);
    			if(q1.size() > q2.size()) { q2.push(-q1.top()); q1.pop(); }
    			if(q2.size() > q1.size()+1 ) { q1.push(-q2.top()); q2.pop(); }
    			if(i&1){
    				 printf("%d%c",-q2.top(),i==M?'\n':' ');
                	 if(i%20==19)printf("\n");
				}
			}
	}
}