算法入门-对顶堆(优先队列)-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():踢出队首

全部评论

相关推荐

湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:11
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务