算法入门-对顶堆(优先队列)-Running Median
Running Median
https://ac.nowcoder.com/acm/problem/50940
题意
- 输入一个序列,每当该序列元素个数为奇数个的时候,就输出中位数
思路
- 对顶堆维护整个序列,大顶堆维护前一半,小顶堆维护后一半,如果进入的元素比小顶堆的堆顶小,就放入大顶堆
- 每次放完元素后维护两个堆,使奇数个时小顶堆的元素个数总比大顶堆多1,这样子中位数就在小顶堆的堆顶,输出即可
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;;
scanf("%d",&t);
while(t--){
int idx,n;
scanf("%d%d",&idx,&n);
priority_queue<int,vector<int>,greater<int>>a;//小顶堆
priority_queue<int,vector<int>,less<int>>b;//大顶堆
int cnt=0;
printf("%d %d\n",idx,n/2+1);
for(int i=1;i<=n;i++){
int tp;
scanf("%d",&tp);
if(!a.empty()&&tp<a.top()) b.push(tp);
else a.push(tp);
while(a.size()-b.size()>1){
b.push(a.top());
a.pop();
}
while(a.size()-b.size()<1){
a.push(b.top());
b.pop();
}
if((a.size()+b.size())%2){
printf("%d ",a.top());
cnt++;
if(cnt%10==0||i==n){
printf("\n");
}
}
}
}
return 0;
}
priority_queue
-
priority_queue<类型>名称
-
priority_queue<类型,vector<类型>,比较方法>名称
-
比较方法包含:
大顶堆:less<类型>
小顶堆:greater<类型>
自定义:结构体重载
struct cmp { bool operator()(const int& a, const int& b) { return a>b;//无限制 } };
-
方法:
top():队首
size():大小
empty():空
push():插入
pop():踢出队首