欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【POJ 2259】Team Queue【队列】

程序员文章站 2022-07-14 12:17:28
...

题目大意:

题目链接:http://poj.org/problem?id=2259
t个团队的人正在排一个长队。每次新来一个人时,如果他有队友在排队,那么新人会插队到最后一个队友的身后。如果没有任何一个队友排队,则他会被排到长队的队尾。
要求支持如下3中指令:

  • ENQUEUE x:编号为x的人进入长队。
  • DEQUEUE:长队的队首出队。
  • STOP:停止模拟

对于每个DEQUEUE指令,输出出队的人的编号。


思路:

很明显的队列。但是插队操作却有点难实现。
为了完成插队操作,就要先建n+1个队列。q[0]用来储存团队的排队情况(因为一个团队会在一起),而q[1]q[n]则储存每个团队的人员情况。
每当来了一个人时,就判断这个人的是否有队友在队伍中,如果有,就q[team[x]].push(x)进入团队队列;如果没有,就先将这个团队进入总队列q[0].push(team[x]),再讲这个人进入团队队列q[team[x]].push(x)。出队时,如果出队的人x还有队友在队伍中,那么就直接将x从团队队列中退出q[team[x]].pop();如果没有队友了,那么不仅要然他从团队中退出,而且还要将整个团队从总队列退出q[0].pop()


代码:

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;

int n,m,team[1000001],x,sum;
string s;

int main()
{
    while (++sum)
    {
        scanf("%d",&n);
        if (!n) return 0;
        printf("Scenario #%d\n",sum);
        queue<int> q[1011];  //空间换时间
        memset(team,0,sizeof(team));
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&m);
            for (int j=1;j<=m;j++)
            {
                scanf("%d",&x);
                team[x]=i;
            }
        }
        while (1)
        {
            cin>>s;
            if (s[0]=='S') break;
            if (s[0]=='E')
            {
                scanf("%d",&x);
                if (!q[team[x]].size())  //没有队友
                 q[0].push(team[x]);
                q[team[x]].push(x);
            }
            if (s[0]=='D')
            {
                printf("%d\n",q[q[0].front()].front());  //输出
                q[q[0].front()].pop();
                if (!q[q[0].front()].size()) //没有队友了
                 q[0].pop();
            }
        }
        printf("\n");
    }
}