题目描述

依次读入n个整数，每当读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

输入

第一行输入n(保证为奇数)
第二行输入n个整数，空格隔开

输出

输出(n+1)/2个中位数

样例输入

9
1 2 3 4 5 6 7 8 9

样例输出

1 2 3 4 5

提示

30%数据 n<=39
60%数据 n<=3999
100%数据 n<=199999 -10^9<=输入的整数<=10^9

思路

因为输入的数据过多,所以不能直接排序
可以先确定一个mid,当读入一个值时,如果>=mid,放入一个小根堆A,否则放入一个大根堆B,保证A,B的堆顶是mid左右两侧的数
添加新的值后,会有两种情况,可以默认允许A中比B中多一个值

1. A.size-B.size>=2
   A.top->mid mid->B.top
2. B.size>A.size
   B.top->mid mid->A.top

每次输出mid即可

代码

#include <bits/stdc++.h>
using namespace std;

int n,tmp,now;
priority_queue <int> a;
priority_queue <int> b;
int main(){
    cin>>n;
    cin>>tmp;
    now=tmp;
    cout<<tmp<<endl;
    for (int i=2;i<=n;++i){
        scanf("%d",&tmp);
        if (tmp>now){
            a.push(-tmp);
        }else{
            b.push(tmp);
        }
        int sizea=a.size(),sizeb=b.size();
        if (sizea-sizeb>=2){
            b.push(now);
            if (a.size()){
                now=-a.top();
                a.pop();
            }
        }else if(sizeb>sizea){
            a.push(-now);
            now=b.top();
            b.pop();
        }
        if(i&1) printf("%d\n",now);
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/57/