【ABC298C】题解

fengxiaoyi / 2023-05-06 / 原文

思路

一道很好的复习数据结构的题。

对于第 \(1\) 个问答（既第 \(2\) 种操作），我用一个小根堆（优先队列，\(\text{priority\_queue}\)）来储存第 \(i\) 个盒子的卡牌。

对于第 \(2\) 个问答（既第 \(3\) 种操作），我用一个 \(\text{set}\) 来储存编号为 \(i\) 个卡牌在哪些盒子里。
由于 \(\text{set}\) 会自动去重，也会自动排序，所以直接存和输出了。

怎么存呢？

先看一下我开的变量：

set<int>q2[200010];
priority_queue<int,vector<int>,greater<int> >q1[200010],k;

其中 \(q_1[i]\) 表示第 \(i\) 个盒子里的卡牌（小根堆，升序排序），\(q_2[i]\) 表示编号为 \(i\) 个卡牌在的盒子的编号（也是升序排序），\(k\) 是输出用做过渡的。

设要将编号为 \(a\) 的卡牌放在编号为 \(b\) 的盒子里，则：

q1[b].push(a);
q2[a].insert(b);

看不懂的结合定义再理解一遍。

会存了，询问就直接输出了。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
set<int>q2[200010];
priority_queue<int,vector<int>,greater<int> >q1[200010],k;
int main(){
	scanf("%d%d",&n,&q);
	while(q--){
		int op;
		scanf("%d",&op);
		if(op==1){
			int a,b;
			scanf("%d%d",&a,&b);
			q1[b].push(a);
			q2[a].insert(b);
		}
		else if(op==2){
			int a;
			scanf("%d",&a);
			while(!q1[a].empty()){
				k.push(q1[a].top());
				printf("%d ",q1[a].top());
				q1[a].pop();
			}
			putchar('\n');
			while(!k.empty()){
				q1[a].push(k.top());
				k.pop();
			}
		}
		else{
			int a;
			scanf("%d",&a);
			for(set<int>::iterator it=q2[a].begin();it!=q2[a].end();it++) printf("%d ",*it);
			putchar('\n');
		}
	}
	return 0;
}