例题5-6　团体队列（Team Queue，UVa540）

63 阅读 0 评论 42 点赞

我是靠谱客的博主无奈火，最近开发中收集的这篇文章主要介绍例题5-6　团体队列（Team Queue，UVa540），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2418/5000

队列和优先级队列是大多数计算机科学家都知道的数据结构。该
然而，Team Queue并不是那么出名，尽管它经常出现在日常生活中。午餐时间
例如，在Mensa前面的队列是一个团队队列。
在团队队列中，每个元素都属于一个团队。如果元素进入队列，则首先搜索
队列从头到尾检查是否已经有一些队友（同一队员的成员）
在队列中。如果是，它就会进入它们后面的队列。如果没有，它进入尾部的队列
并成为新的最后元素（运气不好）。像普通队列一样进行出队：元素是
按照它们出现在团队队列中的顺序从头到尾进行处理。
您的任务是编写一个模拟此类团队队列的程序。
输入
输入文件将包含一个或多个测试用例。每个测试用例都以团队数量开始
t（1≤t≤1000）。然后是团队描述，每个描述由元素数量组成
属于团队和元素本身。元素是0..999999范围内的整数。一个
团队可能包含多达1000个元素。
最后，下面是一个命令列表。有三种不同的命令：
•ENQUEUE x - 将元素x输入团队队列
•DEQUEUE - 处理第一个元素并将其从队列中删除
•STOP - 测试用例结束
对于t，输入将以0的值终止。
警告：测试用例最多可包含200000（二十万）个命令，因此执行
团队队列应该是高效的：元素的入队和出队都应该
只花时间。
产量
对于每个测试用例，首先打印一行“Scenario #k”，其中k是测试用例的编号。然后，
对于每个'DEQUEUE'命令，打印在一行上出列的元素。打印一个空白行
在每个测试用例之后，即使在最后一个之后。

Sample Input
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0
Sample Output
Scenario #1
101
102
103
201
202
203
Scenario #2
259001
259002
259003
259004
259005
260001

思路：就是把每个团队都给予一个编号，例如；样例输入1

2 （两组数据）
3 101 102 103 （编号为 0）
3 201 202 203 （编号为 1）

创建两个队列q(团队的队列),q2[maxt](团队i的成员的队列 );

我们再输入入队模拟指令的时候，先判断q2[maxt]是否为空，为空我们就让我们指定的那个编号的队列入队到q2[maxt]；

例如：ENQUEUE 259001，此时259001再编号为0的队列中，此时他是第一个进入q2[maxt]中的编号为0的队列；那么我们就把编号为0 的对列入队，再把259001入到编号为0的队列中；然后我们以后再执行的时候q2[0]就不为空了，当我们想要再入队其他的元素的时候，就可以直接吧这个元素入到0号队列中；其他编号的队列和元素也是如此；输出的时候只要按照q2[maxt]中队列的编号，让每个编号的队列中的首元素根据操作出队就ok

再来看看作者刘汝佳老师的思路，你就会更理解了：

本题有两个队列：每个团队有一个队列，而团队整体又形成一个队列。例如，有3个团队1，2，3，队员集合分别为{101，102，103，104}、{201，202}和{301，302，303}，当前长队为{301，303，103，101，102，201}，则3个团队的队列分别为{103，101，102}、 {201}和{301，303}，团队整体的队列为{3，1，2}

#include<cstdio>
#include<map>
#include<queue>
using namespace std;
const int maxt = 1000+10;

int main()
{
    int t,kase=0;
    while(scanf("%d",&t)==1&&t)
    {
        printf("Scenario #%dn",++kase);

        map<int,int>team;
        for(int i=0;i<t;i++)
        {
            int x,n;
            scanf("%d",&n);
            while(n--)
            {
                scanf("%d",&x);
                team[x] = i;
            }
        }

        queue<int>q,q2[maxt];
        for(;;)
        {
            int x;
            char cmd[10];
            scanf("%s",cmd);
            if(cmd[0]=='S') break;
            else if(cmd[0]=='E')
            {
                if(q2[t].empty())
                    q.push(t);
                q2[t].push(x);
            }
            else if(cmd[0]=='D')
            {
                int t = team[x];
                printf("%d",q2[t].front());
                q2[t].pop();
                if(q2[t].empty())
                    q.pop();
            }
        }
        printf("n");
    }
    return 0;
}