题解：CF1468C Berpizza

xyx4042024-12-062025-01-03

思路：

先考虑用队列和结构体进行模拟。

把输入的那个数的 $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;
}