数据结构 queue

问题描述

t 个团队在餐厅前准备排队。他们的排队规则是：
初始队伍为空。一个人要排进队伍前，先搜索队伍中是否有他的队友。如果
有，这名成员就直接站在最后一个队友的后面，如果没有，那么这名成员只能排
在整个队伍的最后面。排队中途，队首的人可能被要求离开队伍。
依照上述排队规则，给出一些操作，操作有以下两种：
(1) IN x ， – 编号为 x 的成员进入队伍；
(2) OUT ， – 队首成员离开队伍。
操作结束后按顺序输出所有离开成员的编号。

★数据输入
输入第一行为一个正整数 t,代表团队的数量(1<=t<=1000)。
接下来 t 行，每行第一个整数为该团队的人数 n(1<=n<=1000)，接着 n 个整
数代表 n 个成员的编号 id， id 唯一且 1<=id<=1000000。
接下来 q 行操作(1<=q<=200000)，注意可能出现已经在队列中的人重复入队
的情况，忽略这样的操作。

★数据输出
输出第一行为整数 m，离开队伍的成员的数量。
接下来 m 行按序输出离开的成员的 id。

输入示例	输出示例
2 3 101 102 105 3 103 104 106 12 IN 101 IN 103 IN 104 IN 102 IN 105 IN 106 OUT OUT OUT OUT OUT OUT	6 101 102 105 103 104 106

输入示例

输出示例

2
5 2501 2502 2503 2504 2505
6 26001 26002 26003 26004 26005 26006
14
IN 2501
IN 26001
IN 2502
IN 2503
IN 2504
IN 2505
OUT
OUT
IN 2602
IN 2603
OUT
OUT
OUT
OUT

6
2501
2502
2503
2504
2505
26001

思路

　　定义一个存team的队列qq，其中，每个元素team是一个队列。也就是说，定义一个存队列的队列。

　　但是由于qq要支持随机访问，故用数组模拟队列。qq中的每个元素team用std::queue或者数组模拟都可以。

　　由于操作数较多(1<=q<=200000) ，若每次操作依据id查找所属team，再查找team再queue中的位置会消耗较多时间，

　　所以用数组teamid存对应id所属的team编号(从1开始)，用数组teamindex存对应team在qq中的index

　　有新人入队时，先检测他所属的team，若在qq中找到，则push在team末尾；若找不到，则在qq中新加一个team，把这个id加入这个team

　　出队时，对qq中的第1个team实行pop操作，再判断该team是否为空，若为空，对qq pop该team

code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <iostream> 
 5 using namespace std;
 6 #include <queue>
 7 
 8 #define MAXID 1000003
 9 #define MAXTEAM 1003
10 #define MAXOP 200003
11  
12 int teamid[MAXID] = {0};//teamid[id]
13 bool inque[MAXID] = {0}; //inque[id]
14 int teamindex[MAXTEAM] = {0};//teamindex[teamid[id]]
15 
16 queue<int> ans;
17 queue<int> qq[MAXOP];
18 
19 int main()
20 {
21     int i,j,u;
22     int t,id,op;
23     char str[10]={0};
24     scanf("%d",&t);
25     for(i=1;i<=t;i++) 
26     {
27         scanf("%d",&u);
28         for(j=1;j<=u;j++)
29         {
30             scanf("%d",&id);
31             teamid[id] = i;
32         }
33     }
34     
35     int l=1,r=0;
36     scanf("%d",&op);
37     getchar();
38     for(i=1;i<=op;i++)
39     {
40         scanf("%s",str);
41         if(strcmp(str,"IN")==0)
42         {
43             scanf("%d",&id);
44             getchar();
45             if(inque[id]==false)
46             {
47                 inque[id] = true;
48                 if(teamindex[teamid[id]]==0)
49                 {
50                     ++r;
51                     qq[r].push(id);
52                     teamindex[teamid[id]] = r;
53                 }
54                 else
55                 {
56                     qq[teamindex[teamid[id]]].push(id);
57                 }
58             }
59         }
60         else if(strcmp(str,"OUT")==0)
61         {
62             if(l<=r)
63             {
64                 inque[qq[l].front()] = false;
65                 ans.push(qq[l].front());
66                 int tmp = qq[l].front();
67                 qq[l].pop();
68                 if(qq[l].empty())
69                 {
70                     teamindex[teamid[tmp]] = 0;
71                     ++l;
72                 }
73             }
74         }
75     }
76     
77     printf("%d
",ans.size());
78     while(!ans.empty())
79     {
80         printf("%d
",ans.front());
81         ans.pop();
82     }
83     
84     return 0;
85 }

之前贴的代码有bug (新代码已修正)：

　　（1）在OUT操作时应判断 (l<=r)；

　　（2）qq数组定义过小，重新定义为 queue<int> qq[MAXOP];，其中 MAXOP = 200003

　　　　注意，qq数组最好在全局定义，不然OJ上会SO