大根堆+小根堆 中位数（洛谷P1168）

中位数

题目描述：
给你n个非负整数，求 a 1 a_1 a1​, a 1 − a 3 a_1-a_3 a1​−a3​, a 1 − a 5 a_1-a_5 a1​−a5​, a 1 − a 2 k − 1 a_1-a_{2k-1} a1​−a2k−1​的中位数，即前1,3,5,…个数的中位数。

---

这道题的解法比较多，可以用权值线段树，这里介绍堆的写法（优先队列）；求1-n的中位数，最简单地写法就是1-n排序，输出中间的数，但复杂度爆炸；可以用一个大根堆和一个小根堆来实现，大根堆维护前一半小，小根堆维护后一半大，使它们堆的大小相差为1，这个相差的的就是中位数；

#includebits/stdc++.h
using namespace std;
priority_queue int,vectorint,greaterint qu1;//小根堆 
priority_queue int,vectorint qu2;//大根堆 
int main(){
	int n;
	scanf("%d",n);
	int x;
	scanf("%d",x);
	printf("%d\n",x);
	qu2.push(x);
	for(int i=2;i=n;i++){
		scanf("%d",x);
		if(xqu2.top()) qu1.push(x);
		else qu2.push(x);
		while(qu1.size()qu2.size()+1||qu2.size()qu1.size()+1){
			if(qu1.size()qu2.size()){
				qu2.push(qu1.top());
				qu1.pop();
			}
			else{
				qu1.push(qu2.top());
				qu2.pop();
			}
		}
		if(i1){
			if(qu1.size()qu2.size()) printf("%d\n",qu1.top());
			else printf("%d\n",qu2.top());
		}
	}
	return 0;
}