POJ2259Team Queue 队列

题目

Queues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa is a team queue, for example.

In a team queue each element belongs to a team. If an element enters the queue, it first searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue.

Your task is to write a program that simulates such a team queue.
有n个小组要进行排队，每个小组中有若干个人。当一个人来到队伍时，如果队伍中已经有自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。给定不超过2*100000个入队指令（编号为x的人来到队伍）和出队指令（队头的人出队），输出出队的顺序。

题解

可以把每个人的编号用桶装起来，然后读入指令时用Q0$Q_0$存小组入队情况，Qi$Q_i$存每个小组具体入队情况，然后每个人入队、出队时具体判断就可以了

代码

#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

int n,t;
int a[1000006],b[1003];
queue<int> q[1003];

int main(){
    scanf("%d",&n);
    while (n){
        printf("Scenario #%d\n",++t);
        for (int i=1;i<=n;i++){
            int c;
            scanf("%d",&c);
            while (c--){
                int x;
                scanf("%d",&x);
                a[x]=i;
            }
        }
        char ch[8];
        for (int i=0;i<=n;i++)
            while (q[i].size())
                q[i].pop();
        memset(b,0,sizeof(b));
        scanf("%s",ch);
        while (ch[0]!='S'){
            if (ch[0]=='E'){
                int x;
                scanf("%d",&x);
                if (b[a[x]]){
                    q[a[x]].push(x);
                } else {
                    b[a[x]]=1;
                    q[0].push(a[x]);
                    q[a[x]].push(x); 
                }
            }
            if (ch[0]=='D'){
                int x=q[0].front();
                printf("%d\n",q[x].front());
                q[x].pop();
                if (q[x].empty()) q[0].pop(),b[x]=0;
            }
            scanf("%s",ch);
        }
        printf("\n"); 
        scanf("%d",&n);
    }
}