P1801 黑匣子 – Xhesica's blog

链接：Miku

在做这个题之前我做了1168，所以该出来了个这

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;
 priority_queue <int,vector<int>,greater<int> > q1;//小顶 
 priority_queue <int,vector<int>,less<int> >q2;//大顶 
 queue <int>tol;
 int n,k;
int m; 
int a[2000006],u[2000006];
int x;
int f=1;
int tim;
int ans;
void get(int g){
    if(g<=q2.size()){
        for(int j=q2.size()-g+1;j;j--){
            tol.push(q2.top());
            q2.pop();
        }
        cout<<tol.front()<<endl;
        while(!tol.empty()){
            q2.push(tol.front());
            tol.pop();
        }
    }else{
        for(int j=g-q2.size();j;--j){
            tol.push(q1.top());
            q1.pop();
        }
        cout<<tol.front()<<endl;
        while(!tol.empty()){
            q1.push(tol.front());
            tol.pop();
        }
    }
    return ;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;++i){
        scanf("%d",&u[i]);
    }
    for(int i=1;i<=n;++i){
        k=a[i];
        if(i==1){
        q2.push(k);
        }
        else{
            if(q2.top()>k)
            q2.push(k);
            else
            q1.push(k);
        }
        if(q2.size()>q1.size()&&q2.size()-q1.size()>1){
            x=q2.top();
            q1.push(x);
            q2.pop();
        }
        if(q1.size()>q2.size()&&q1.size()-q2.size()>1){
            x=q1.top();
            q2.push(x);
            q1.pop();    
        }
        while(i==u[f]){
    //        cout<<3432<<endl;
            f++;
            tim++;
            get(tim);
        }
    }
//    cout<<f<<endl;
    return 0;
}

红黑配

它不对

虽然说还是对顶堆，但是既然要求第I小的数，那么前面那个大根堆我光放i个数，然后直接输出堆顶就行了。

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
 priority_queue <int,vector<int>,greater<int> > q1;//小顶 
 priority_queue <int,vector<int>,less<int> >q2;//大顶 
 queue <int>tol;
 int n,k;
int m; 
int a[2000006],u[2000006];
int x;
int f=1;
int tim=1;
int ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;++i){
        scanf("%d",&u[i]);
    }
    for(int i=1;i<=n;++i){
        if(i==1){
            q2.push(a[i]);
        }else if(a[i]>q2.top()){
            q1.push(a[i]);
        }
        else{
            q2.push(a[i]);
        }
        while(i==u[f]){
            while(q2.size()<tim){//维持数量 
                q2.push(q1.top());
                q1.pop();
            }
            while(q2.size()>tim){
                q1.push(q2.top());
                q2.pop();
            }
            printf("%dn",q2.top());
            f++;
            tim++;
        }
    }
    return 0;
}

发送评论 编辑评论

发送评论编辑评论