AcWing 106 动态中位数 (对顶堆)

https://www.acwing.com/problem/content/108/

维护一个大根堆，一个小根堆，设当前序列长度为\(M\)
当前序列从小到大排名\(1~M/2\)的整数存在大根堆
排名\(M/2+1~M\)的整数存在小根堆，
如果插入后某一堆元素过多，就把该堆堆顶取出来插入令一个堆，
这样序列的中位数就是小根堆的堆顶

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 100010;

int T, n, Case, cnt;
int ans[maxn];
priority_queue<int> qma;
priority_queue<int, vector<int>, greater<int> > qmi;

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); } return s*f; }

int main(){
	T = read();
	while(T--){
		while(!qma.empty()) qma.pop();
		while(!qmi.empty()) qmi.pop();
		
		cnt = 0;
		Case = read(), n = read();
		int x;
		for(int i=1;i<=n;++i){
			x = read();
			if(i==1) qmi.push(x);
			else{
				if(x < qmi.top()) qma.push(x);
				else qmi.push(x);
			} 
			
			while(qma.size() > (i/2)){
				int tmp = qma.top();
				qmi.push(tmp);
				qma.pop();
			}
			int S;
			if(i%2 == 1) S = i/2 + 1;
			else S = i/2;
			while(qmi.size() > S){
				int tmp = qmi.top();
				qma.push(tmp);
				qmi.pop();
			}
			
			if(i%2 == 1) ans[++cnt] = qmi.top();
		}
		
		printf("%d %d\n",Case,cnt);
		int tot = 0;
		for(int i=1;i<=cnt;++i){
			if(tot == 10){ printf("\n"); tot = 0; }
			printf("%d ",ans[i]);
			++tot;
		}printf("\n"); 
	}
	return 0;
}

AcWing 106 动态中位数 (对顶堆)

原文：https://www.cnblogs.com/tuchen/p/13928773.html