【POJ2259】Team Queue（队列，模拟）

problem

• 有n个小组，进行排队。
• 当一个人来到队伍时，若队伍中有自己小组成员时，他就直接站到其后面
• 如果没有，则站到队伍最后面，形成自己小组的第一个入队元素。
• 出队列时，给出出队指令，输出出队成员号码。

solution

• 维护一个队列数组q和总队列p，分别表示每个小组在队伍中的人和队伍中的小组id
• 当x来到队列时，直接加入q[c[x]]末位（c表示x所属的小组）；如果之前为空还要将c[x]加入p中；
• 当出队时，将p首元素（第一个小组）的第一个元素出队；如果p首元素（第一个小组）为空，将p首元素也删除。

codes

#include<cstdio>
#include<iostream>
#include<deque>
#include<string>
#define maxn 100000010
using namespace std;
int n, c[maxn];
deque<int>q[1010], p;
string s;
int main(){
    int count = 0;
    while(cin>>n &&n){
        p.clear();
        for(int i = 1; i <= n; i++)q[i].clear();
        for(int i = 1; i <= n; i++){
            int m;  cin>>m;
            for(int j = 1; j <= m; j++){
                int x;  cin>>x;  c[x]= i;
            }
        }
        printf("Scenario #%d
", ++count);
        while(cin>>s && s[0]!='S'){
            if(s[0]=='E'){
                int x;  cin>>x;
                if(!q[c[x]].size())p.push_back(c[x]);
                q[c[x]].push_back(x);
            }else{
                int x = p.front();
                printf("%d
", q[x].front());
                q[x].pop_front();
                if(!q[x].size())p.pop_front();
            }
        }
        cout<<'
';
    }
    return 0;
}