#队列#poj 2259 Team Queue

题目

有n$n$个小组排队，当一个人来到队伍时，若队伍没有小组成员，则排在队尾，否则插在小组最后面，对于每一个出队指令，输出每一个人。

---

分析

可以用一个大的队列装入小组的编号，当小组没人时创建一个新的小组编号并不断入队，出队时则判断小组的人数是否为0，若无人就退出大队列。

---

代码

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
queue<int>q[1005]; int n,answer; short a[1000001];
int in(){
    int ans=0; char c=getchar();
    while (c<48||c>57) c=getchar();
    while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
    return ans;
}
int main(){
    while (1){
        n=in(); char c; int k;
        if (!n) return 0;  memset(a,0,sizeof(a));
        printf("Scenario #%d\n",++answer);
        for (int i=1;i<=n;i++){
            k=in();
            for (int j=1;j<=k;j++) a[in()]=i;//用桶装入
        }
        for (int i=0;i<=n;i++) while (q[i].size()) q[i].pop();//清空队列
        while ((c=getchar())!='S'){
            bool flag=0;
            if (c=='D') flag=1;
            while (c>64&&c<91) c=getchar();
            if (flag){
                printf("%d\n",q[q[0].front()].front());//输出第一个
                q[q[0].front()].pop(); //出队
                if (!q[q[0].front()].size()) q[0].pop();//如果没有小组成员则弹出编号
            }   
            else{
                k=in();
                q[a[k]].push(k);//入队
                if (q[a[k]].size()==1) q[0].push(a[k]);//创建新的编号
            }   
        }
        putchar('\n');
    }
}