ABC217 E (优先队列+模拟)

题目链接在这里：E - Sorting Queries (atcoder.jp)

这题我们会发现如果它让你排序你就每次都排序的话是(n^2)logn的复杂度，必然超时。但是如果开一个优先队列，每次需要排序的时候只把新加入的数放到优先队列里面，时间复杂度就变成了nlogn

想到了正解然后算错了复杂度就没写可太草了！

#include "bits/stdc++.h"
using namespace std;
const int MAX=2e6+5;
int n;
priority_queue <int,vector<int>,greater<int> > q;
int a[MAX];
int main(){
    freopen ("e.in","r",stdin);
    freopen ("e.out","w",stdout);
    int i,j,x,y,zt;
    int head=1,tail=0;
    scanf("%d",&n);
    for (i=1;i<=n;i++){
        scanf("%d",&x);
//        cout<<x<<" ????"<<endl;
        if (x==1){
            scanf("%d",&y);
            a[++tail]=y;
        }
        if (x==2){
            if (!q.empty()){
                zt=q.top(),q.pop();
                printf("%d
",zt);
            }
            else{
                printf("%d
",a[head]);
                head++;
            }
        }
        if (x==3){
            for (j=head;j<=tail;j++) q.push(a[j]);
            head=tail+1;
        }
    }
    return 0;
}