萌新求助：我的对顶堆算法哪里有问题

Gavin0576 @ 2020-01-26 14:27:22

#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;
    cin>>n;
    int input;
    cin>>input;
    q1.push(input);
    cout<<input<<endl;
    for(int i=2;i<=n;i++){
        cin>>input;
        if(input>=q1.top()) q2.push(input);
        else q1.push(input);
        if(!i%2){
            while(q1.size()!=q2.size()){
                if(q1.size()>q2.size()){
                    q2.push(q1.top());
                    q1.pop();
                }
                else{
                    q1.push(q2.top());
                    q2.pop();
                }
            } 

        }
        else if(i%2){
            if(q1.size()>q2.size()) cout<<q1.top()<<endl;
            else cout<<q2.top()<<endl;
        }
    }
    return 0;
}

by Gavin0576 @ 2020-01-26 14:28:38

提交了全WA

by D447H @ 2020-02-27 12:30:08

您对拍了吗？

by raincity @ 2020-03-07 15:47:13

你可以跟我对拍一下，对顶堆算法：

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

const int N=100005;
int heap[N],a[N],n;
struct lowint{
    int data;
    bool friend operator <(const lowint &a,const lowint &b){
        return a.data>b.data;
    }
};
struct highint{
    int data;
    bool friend operator <(const highint &a,const highint &b){
        return a.data<b.data;
    }
};
priority_queue<lowint> low;
priority_queue<highint> high;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    printf("%d\n",a[1]);
    lowint x;highint y;
    x.data=a[1];
    low.push(x);
    for(int i=3;i<=n;i+=2){
        if(a[i-1]<low.top().data) y.data=a[i-1],high.push(y);
        else x.data=a[i-1],low.push(x);
        if(high.size()>(i-1)/2) x.data=high.top().data,low.push(x),high.pop();
        else if(low.size()>i/2) y.data=low.top().data,high.push(y),low.pop();

        if(a[i]<low.top().data) y.data=a[i],high.push(y);
        else x.data=a[i],low.push(x);
        if(high.size()>i/2) x.data=high.top().data,low.push(x),high.pop();
        else if(low.size()>(i+1)/2) y.data=low.top().data,high.push(y),low.pop();

        printf("%d\n",low.top().data);
    }
    return 0;
}

by 张宸琳 @ 2020-07-01 16:31:38

抱灵蒟蒻也来求助了，同样是对顶堆，今天刚学

楼上大佬的代码看不懂没法对拍抱歉

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

int main()
{
    priority_queue<int,vector<int>,greater<int> > minpq; 
    priority_queue<int> maxpq;
    int n,a,b;
    cin>>n>>a;
    maxpq.push(a);
    cout<<a;
    for(int i=1;i<n;i+=2)
    {
        cin>>a>>b;
        maxpq.push(a);
        maxpq.push(b);
        minpq.push(maxpq.top());
        maxpq.pop();
        if(maxpq.top()>minpq.top())
        {
            int x=maxpq.top();
            maxpq.pop();
            maxpq.push(minpq.top());
            minpq.pop();
            minpq.push(x);
        }
        cout<<endl<<maxpq.top();
    }
    return 0;
}

by xuekaiwen_emmm @ 2023-01-02 22:01:46

全都是假萌新，真萌新瑟瑟发抖