欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

对顶堆

程序员文章站 2022-03-31 20:02:48
...

洛谷 1168 中位数

题目描述

给出一个长度为NN的非负整数序列A_iAi​,对于所有1≤k≤(N+1)/2,输出A1​,A3​,…,A2k−1​的中位数。即前1,3,5,…个数的中位数。

输入格式

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

第2行包含N个非负整数Ai​(Ai​≤10^9)。

输出格式

共(N+1)/2行,第i行为A1​,A3​,…,A2k−1​的中位数。

输入输出样例

输入 

7
1 3 5 7 9 11 6

输出 

1
3
5
6

说明/提示

对于20\%20%的数据,N ≤ 100N≤100;

对于40\%40%的数据,N ≤ 3000N≤3000;

对于100\%100%的数据,N ≤ 100000N≤100000。

解析:

使用两个堆,大根堆维护较小的值,小根堆维护较大的值,即大根堆的堆顶是较小的数中最大的,小根堆的堆顶是较大的数中最小的

将大于大根堆堆顶的数(比所有大根堆中的元素都大)的数放入小根堆,小于等于大根堆堆顶的数(比所有小根堆中的元素都小)的数放入大根堆,那么就保证了所有大根堆中的元素都小于小根堆中的元素

于是我们发现对于大根堆的堆顶元素,有【小根堆的元素个数】个元素比该元素大,【大根堆的元素个数-1】个元素比该元素小;同理,对于小跟堆的堆顶元素,有【大根堆的元素个数】个元素比该元素小,【小根堆的元素个数-1】个元素比该元素大;

那么维护【大根堆的元素个数】和【小根堆的元素个数】差值不大于1之后,元素个数较多的堆的堆顶元素即为当前中位数;(如果元素个数相同,那么就是两个堆堆顶元素的平均数,本题不会出现这种情况)

根据这两个堆的定义,维护方式也很简单,把元素个数多的堆的堆顶元素取出,放入元素个数少的堆即可

对顶堆

AC代码:

#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int> >Q1;//大根堆,维护较小的数值
priority_queue<int,vector<int>,greater<int> >Q2;//小根堆,维护较大的数值
int main(){
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(!Q1.empty()&&x<=Q1.top()) Q1.push(x);
        else if(!Q2.empty()&&x>Q2.top()) Q2.push(x);
        else Q2.push(x);
        //调整堆的大小,满足(小顶堆元素个数)-(大顶堆元素个数)= 1
        if(Q1.size()>Q2.size()){
            Q2.push(Q1.top());
            Q1.pop();
        }
        else if(Q2.size()>Q1.size()+1){
            Q1.push(Q2.top());
            Q2.pop();
        }
        if(i%2==1) printf("%d\n",Q2.top());
    }    
    return 0;
}

 

 

 

相关标签: