思路： #
先考虑用队列和结构体进行模拟。
把输入的那个数的 $id$ 和值一起放进队列，然后照着题目模拟就可以得出代码。
struct node{
int id;
int num;
};
queue<node>dl,d;
int main(){
cin>>n;
while(n--){
cin>>op;
if(op==1){
int x;cin>>x;
dl.push({++i,x});
}
else if(op==2){
cout<<dl.front().id<<" ";
dl.pop();
}
else if(op==3){
queue<node>d;
int id=0;
int maxx=-5;
int cnt=0;
while(dl.empty()==0){
node tamp=dl.front();
dl.pop();
d.push(tamp);
if(tamp.num>maxx){
maxx=tamp.num;
id=tamp.id;
}
}
while(d.empty()==0){
node tamp=d.front();
d.pop();
if(tamp.id!=id)dl.push(tamp);
else cout<<tamp.id<<" ";
}
}
}
return 0;
}
提交后发现超时了，考虑怎么优化。
因为 $id$ 是唯一的，所以我们可以使用一个数组把输出过的 $id$ 进行标记，也就是这个 $id$ 表示的数被删除了，然后使用 priority_queue 处理操作 $3$，注意要输出最大的没有被删除的最早加入堆的数的 $id$。
代码： #
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int n;
int op;
int i;
bool bj[int(5*1e5+10)];
struct node{
int id;
int num;
friend bool operator<(const node &a,const node &b){
return a.num==b.num?a.id>b.id:a.num<b.num;
}
};
int last=1;
priority_queue<node>dl;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
while(n--){
cin>>op;
if(op==1){
int x;cin>>x;
dl.push({++i,x});
}
else if(op==2){
while(1){
if(!bj[last]){
cout<<last<<" ";
bj[last]=1;
break;
}
last++;
}
}
else if(op==3){
while(bj[dl.top().id])dl.pop();
cout<<dl.top().id<<" ";
bj[dl.top().id]=1;
dl.pop();
}
}
return 0;
}