P1168 中位数

P1168 中位数

题目描述

给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A₁, A₁～A₃, …, A₁～A_2K-1的中位数。即前1，3，5，……个数的中位数。

输入输出格式

输入格式：

　　第1行为一个正整数N，表示了序列长度。　　

　　第2行包含N个非负整数A_i (A_i≤ 10⁹)。

输出格式：

　　共（N+1）/2行，第i行为A₁，A₃......A_2K-1　的中位数。　

输入输出样例

　　输入 #1

7
1 3 5 7 9 11 6

　输出 #1

1
3
5
6

说明/提示

说明

对于20%的数据，N ≤ 100；

对于40%的数据，N ≤ 3000；

对于100%的数据，N ≤ 100000.

对顶堆

顾名思义，对顶堆是两个堆组成的特殊的数据结构

手画有点丑
如果说上面是个小根堆，下面是个大根堆，小根堆的元素都大于大根堆的元素，那么我们可以发现：
每一层节点从上往下逐层递减

维护两个堆：

1. 大根堆存储较小的一半

2. 小根堆存储较大的一半

3. 默认大根堆的size≥sizegeq size≥小根堆

4. 在读入时，若该数为第奇数个，则将它入大根堆

5. 若为第偶数个，则入小根堆

6. 一旦大根堆堆顶>>>小根堆堆顶，则交换

7. 逢第奇数个输出大根堆堆顶

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,a,x,y;
priority_queue<int>Max;//小半部分大根堆
priority_queue<int,vector<int>,greater<int> >Min;//大半部分小根堆
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%d",&a);
		if(i&1){
			Max.push(a);
		} else {
			Min.push(a);
		}
		if(!Max.empty()&&!Min.empty()&&Max.top()>Min.top()){
			x=Max.top();
			y=Min.top();
			Max.pop();
			Min.pop();
			Max.push(y);
			Min.push(x);
		}
		if(i&1)printf("%d
",Max.top());
	}
	return 0;
}