『题解』A21561中位数

使用两个堆，大根堆维护较小的值，小根堆维护较大的值

即小根堆的堆顶是较大的数中最小的，大根堆的堆顶是较小的数中最大的

将大于大根堆堆顶的数（比所有大根堆中的元素都大）的数放入小根堆，小于等于大根堆堆顶的数（比所有小根堆中的元素都小）的数放入大根堆

那么就保证了所有大根堆中的元素都小于小根堆中的元素

于是我们发现对于大根堆的堆顶元素，有【小根堆的元素个数】个元素比该元素大，【大根堆的元素个数-1】个元素比该元素小；

同理，对于小跟堆的堆顶元素，有【大根堆的元素个数】个元素比该元素小，【小根堆的元素个数-1】个元素比该元素大；

那么维护【大根堆的元素个数】和【小根堆的元素个数】差值不大于1之后，元素个数较多的堆的堆顶元素即为当前中位数；（如果元素个数相同，那么就是两个堆堆顶元素的平均数，本题不会出现这种情况）

根据这两个堆的定义，维护方式也很简单，把元素个数多的堆的堆顶元素取出，放入元素个数少的堆即可

好了，下面上代码

#include <bits/stdc++.h>
using namespace std;
priority_queue <int, vector<int>, greater<int> > q2;
priority_queue <int> q;
int main(){
	int n;
	cin >> n;
	int x;
	cin >> x;
	q.push(x);
	cout << x << endl;
	for (int i = 2; i <= n; i++){
		cin >> x;
		if (x <= q.top()){
			q.push(x);
		}
		else{
			q2.push(x);
		}
		while (int(q.size()) > int(q2.size())){
			int y = q.top();
			q2.push(y);
			q.pop();
		}
		while (int(q2.size()) > int(q.size())){
			int y = q2.top();
			q.push(y);
			q2.pop();
		}
		if (i % 2 == 1){
			cout << q.top() << endl;
		}
	}
	return 0;
}