ABC217 E (优先队列+模拟)

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

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

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

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=2e6+5;
 4 int n;
 5 priority_queue <int,vector<int>,greater<int> > q;
 6 int a[MAX];
 7 int main(){
 8     freopen ("e.in","r",stdin);
 9     freopen ("e.out","w",stdout);
10     int i,j,x,y,zt;
11     int head=1,tail=0;
12     scanf("%d",&n);
13     for (i=1;i<=n;i++){
14         scanf("%d",&x);
15 //        cout<<x<<" ????"<<endl;
16         if (x==1){
17             scanf("%d",&y);
18             a[++tail]=y;
19         }
20         if (x==2){
21             if (!q.empty()){
22                 zt=q.top(),q.pop();
23                 printf("%d\n",zt);
24             }
25             else{
26                 printf("%d\n",a[head]);
27                 head++;
28             }
29         }
30         if (x==3){
31             for (j=head;j<=tail;j++) q.push(a[j]);
32             head=tail+1;
33         }
34     }
35     return 0;
36 }

 

ABC217 E (优先队列+模拟)

上一篇:高中3年数学知识梳理 & 成考 高数对比;


下一篇:centos7设置静态IP地址