【POJ3784】Running Median(中位数,对顶堆)

            

description

输入M个数,当已输入的个数为奇数个时输出此时的中位数。
一共有M/2+1个中位数要输出,每一行10个。

solution

维护两个优先队列。
大根堆q1维护比当前中位数小的元素。
小跟堆q2维护比当前中位数大的元素。

我们把中位数放在大根堆q1的堆顶,于是有:
输入的数为奇数个时:q1.size()=q2.size()+1 (多一个中位数)
输入的数为偶数个时:q1.size()=q2.size() (不存在中位数)

codes

#include
#include
using namespace std;
priority_queue<int>q1;//big
priority_queue<int,vector<int>,greater<int> >q2;
int main(){
    int T;  cin>>T;
    while(T--){
        while(q1.size())q1.pop();
        while(q2.size())q2.pop();

        int cas, n;
        cin>>cas>>n;
        cout<' '<<(n+1)/2<<'\n';
        for(int i = 1; i <= n; i++){
            int x;  cin>>x;

            if(q1.empty())q1.push(x);
            else{
                if(x>q1.top())q2.push(x);
                else q1.push(x);
            }

            while(q1.size()while(q1.size()>q2.size()+1){
                q2.push(q1.top());  q1.pop();
            }

            if(i&1)cout<' ';
            if(!(i%20))cout<<'\n';
        }

        cout<<'\n';
    }
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像