0x00 前言
自己整了个翻译呢
一开始写的超级复杂
后开借鉴别人思路才知道其实不长
0x01 读题
在团队队列中,每个元素都属于一个团队。
如果元素进入队列。它首先从头到尾搜索队列,检查它的一些团队成员(同一团队的元素)是否已经在队列中。如果是,它就插入它们的后面。如果不是,它将在尾部进入队列并成为新的最后一个元素。
退出队列的操作与普通队列类似:元素按照它们在团队队列中出现的顺序从头到尾进行处理。
您的任务是编写一个程序来模拟这样的团队队列。
输入文件将包含一个或多个测试样例。
每个测试样例从团队数量 \(t\ (1 <t< 1000)\) 开始。
接下来是对团队的描述,每个描述包含属于团队的元素的数量和元素本身。元素是 \(\left[0,1000000\right)\) 范围内的整数。一个团队可能由多达 \(1000\) 个元素组成。
最后,下面是一个命令列表。有三种不同的命令:
-
\(\mathtt{ENQUEUE}\ x\):在团队队列中输入元素 \(x\)
-
\(\mathtt{DEQUEUE}\):处理第一个元素并将其从队列中移除
-
\(\mathtt{STOP}\):结束测试用例
测试样例结束时输入 \(0\)
警告:一个测试样例可能包含多达 \(200000\) 个命令,因此查询和退出一个元素应该只花费常量时间。
对于每个测试用例,首先打印一行\(Scenario #k\),其中 \(k\) 是测试样例的编号。
然后,对于每个 \(\mathtt{DEQUEUE}\) 的命令,在一行中输出被退出队列的元素。
在每个测试样例之后输出空行,在最后一个测试样例之后也是如此。
0x02 分析
模拟,它是个模拟
不废话了
0x03 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200100;
inline ll read(){
ll x=0,y=1;
char c=getchar();
while (c<'0'||c>'9'){
if(c=='-')
y=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*y;
}
int main(){
int t,m=1;
while(cin>>t&&t){
map<int,int> v;
for(int i=1;i<=t;i++){
int n;
n=read();
while(n--){
int x;
x=read();
v[x]=i;
}
}
cout<<"Scenario #"<<m++<<endl;
queue<int> team[N];
queue<int> total;
string op;
while(cin>>op){
if(op=="STOP")
break;
if(op=="ENQUEUE"){
int x;
x=read();
int t=v[x];
if(team[t].empty())
total.push(t);
team[t].push(x);
}
if(op=="DEQUEUE"){
if(!total.empty()){
int t=total.front();
cout<<team[t].front()<<endl;
team[t].pop();
if(team[t].empty())
total.pop();
}
}
}
printf("\n");
}
return 0;
}