本文共 2048 字，大约阅读时间需要 6 分钟。

题目描述：

有n个小组要排成一个队列，每个小组中有若干人。当一个人来到队列时，如果队列中已经有了自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。请你编写一个程序，模拟这种小组队列。

输入格式：

输入将包含一个或多个测试用例。对于每个测试用例，第一行输入小组数量t。接下来t行，每行输入一个小组描述，第一个数表示这个小组的人数，接下来的数表示这个小组的人的编号。编号是0到999999范围内的整数。一个小组最多可包含1000个人。

最后，命令列表如下。 有三种不同的命令：

1、ENQUEUE x - 将编号是x的人插入队列；

2、DEQUEUE - 让整个队列的第一个人出队；

3、STOP - 测试用例结束

每个命令占一行。当输入用例t=0时，代表停止输入。需注意：测试用例最多可包含200000（20万）个命令，因此小组队列的实现应该是高效的，入队和出队都需要使用常数时间。

输出样例

对于每个测试用例，首先输出一行“Scenario #k”，其中k是测试用例的编号。然后，对于每个DEQUEUE命令，输出出队的人的编号，每个编号占一行。在每个测试用例（包括最后一个测试用例）输出完成后，输出一个空行。

数据范围

1≤t≤1000

输入样例：

23 101 102 1033 201 202 203ENQUEUE 101ENQUEUE 201ENQUEUE 102ENQUEUE 202ENQUEUE 103ENQUEUE 203DEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP25 259001 259002 259003 259004 2590056 260001 260002 260003 260004 260005 260006ENQUEUE 259001ENQUEUE 260001ENQUEUE 259002ENQUEUE 259003ENQUEUE 259004ENQUEUE 259005DEQUEUEDEQUEUEENQUEUE 260002ENQUEUE 260003DEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP0

输出样例：

Scenario #1101102103201202203Scenario #2259001259002259003259004259005260001

分析：

本题要求实现一个小组队列，具体做法是给每个小组维护一个队列，另外再维护一个总的队列。总队列里只需排各个小组的编号，一旦有人新加入队列，首先判断此前其小组队列是否为空，是则将小组的编号加入总队列，再将此人加入小组队列即可；若其小组队列不为空，则直接加入小组队列即可。执行出队操作时，首先从总队列里取得队头小组的编号，并且将该小组队列队头元素出队，出队后一旦该小组队列为空，则同时将该小组队列的编号从总队列中出队。

思路十分简单，唯一要注意的是入队时要快速判断此人属于哪个小组，采用哈希表可解决。因为任意一个人的编号在一百万以内，所以在读入各小组成员时就可以构建哈希映射，便于后续入队时在O（1）时间内找到小组队列。

#include 
   
    #include 
    
     using namespace std;const int maxn = 1000005;int m[maxn];int main(){    ios::sync_with_stdio(false);    int n;    int cnt = 1;    while(cin>>n,n){        cout<<"Scenario #"<
     
      <
      
       < n;i++){            cin>>nums;            while(nums--){                cin>>x;                m[x] = i;            }        }        queue
       
         total,person[n];        string s;        while(cin>>s,s != "STOP"){            if(s == "ENQUEUE"){                cin>>x;                int u = m[x];                if(person[u].empty())   total.push(u);                person[u].push(x);            }            else{                int u = total.front();                cout<
        
         <
        
       
      
     
    
   

转载地址：https://blog.csdn.net/qq_30277239/article/details/89849432 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！