大根堆+小根堆 中位数(洛谷P1168)

中位数

题目描述:
给你n个非负整数,求 a 1 a_1 a1, a 1 − a 3 a_1-a_3 a1a3, a 1 − a 5 a_1-a_5 a1a5, a 1 − a 2 k − 1 a_1-a_{2k-1} a1a2k1的中位数,即前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;
}
最新回复(0)
/jishuRqTAb52pHxcnkAfI6X5VisBSWqdr0_2FtYLy9S0Q_3D_3D4795016
8 简首页