【算法竞赛进阶指南】POJ3784Running Median

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法竞赛进阶指南】POJ3784Running Median，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1138字，纯文字阅读大概需要2分钟。

内容图文

在算法竞赛进阶指南的第一章中利用堆的特性，我这里直接利用优先队列，不过做起来我做的有点麻烦，重载运算符，最关键的问题是，格式我还调了半天，诶；

#include<iostream>
#include<queue>
using namespace std;

struct rec{
    int num;
};
struct rev{
    int num;
};

bool operator <(const rec &a, const rec &b){
    return a.num>b.num;
}
bool operator <(const rev &a, const rev &b){
    return a.num<b.num;
}

priority_queue<rev>mx;
priority_queue<rec>mi;

void test(){
    while(mx.size()>mi.size()+1 || mi.size()>mx.size()){
        if(mx.size()>mi.size()+1){
            rev tmp1;
            rec tmp2;
            tmp1=mx.top();
            mx.pop();
            tmp2.num=tmp1.num;
            mi.push(tmp2);
        }
        if(mi.size()>mx.size()){
            rev tmp1;
            rec tmp2;
            tmp2=mi.top();
            mi.pop();
            tmp1.num=tmp2.num;
            mx.push(tmp1);
        }
    }
}

int main(){
    int p;
    cin>>p;
    while(p--){
            while(!mi.empty()) mi.pop();
     while(!mx.empty()) mx.pop();
        int n,m;
    cin>>n>>m;
    cout<<n<<" "<<((m+1)>>1)<<"\n";
    int flag=1;
    int kkc=0;
    while(m--){
        int tmp;
        cin>>tmp;
        rev tmp1;
        rec tmp2;

        if(mx.empty()){
            tmp1.num=tmp;
            mx.push(tmp1);
        }else{
            if(tmp<=mx.top().num){
                tmp1.num=tmp;
                mx.push(tmp1);
            }else{
                tmp2.num=tmp;
                mi.push(tmp2);
            }
        }
        test();
        if(flag%2==1) {cout<<mx.top().num<<" ";}
        if(flag%20==19) {cout<<"\n";}
        flag++;
    }
    if(flag%20!=0) {cout<<"\n";}
    }

}

内容总结

以上是互联网集市为您收集整理的【算法竞赛进阶指南】POJ3784Running Median全部内容，希望文章能够帮你解决【算法竞赛进阶指南】POJ3784Running Median所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---