AcWing 132. 小组队列
原题链接
简单
作者:
开心小子
,
2020-06-25 09:34:03
,
所有人可见
,
阅读 564
分析对于本题来说,其实要解决的有两个问题,一是整体上要对每一组进行先后顺序的排序(当第一个组内人数为0时出队),两一个就是对每一个组内进行队列排序。这样其实我们是在维护两个队列。
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1010,M=1000010;//N为小组数上限,M为人数上限
int teamid[M];//teamid将每个人和组数联系起来
int main(){
ios::sync_with_stdio(false);
int n,C=1;
while(cin>>n,n)
{
queue<int > team;//对组进行队列排序
queue<int > person[N];//对每个组进行队列排序
cout<<"Scenario #"<<C++<<endl;
for(int i=0;i<n;i++)
{
int cnt;
cin>>cnt;
while(cnt--)
{
int x;
cin>>x;
teamid[x]=i;//给每个人标上组号
}
}
string command;
while(cin>>command,command!="STOP")
{
if(command=="ENQUEUE")
{
int x,tid;
cin>>x;
tid=teamid[x];//获得当前人的组数
if(person[tid].empty())
team.push(tid);//当当前人所在的组没有人存在时,将组排序到
//队列最后
person[tid].push(x);//将组内进行排序
}
else
{
cout<<person[team.front()].front()<<endl;
//将第一个组的第一个人输出
person[team.front()].pop();//第一个出队
if(person[team.front()].empty())
team.pop(); //当组数队列排序中第一个组内人数为0时,将其出队
}
}
cout<<endl;
}
return 0;
}