紫书刷题进行中，题解系列【GitHub|CSDN】
例题5-6 UVA540 Team Queue（34行AC代码）
题目大意
有一条长队，每个人均唯一属于一个组（有编号），执行给定操作序列，输出相应结果。操作如下：
（假设长队q1）
-
ENQUEUE x：标号为x的人入队，若q1中存在和x属于同一组的人，则将x插入长队中同组的最后一个人之后；否则插入长队最后一个之后 -
DEQUEUE：长队第一个人出队 -
STOP：结束该测试用例
（ps：第一次把题意给看错了，捂脸（：
错误1：只有一条队伍，而我认为每个组就是一个队伍
错误2：误把输入中每组信息当成队列中已有的人
思路分析
题意清晰后，问题变得简单，有多种解决思路，比较朴素的使用链表处理，但这里为了练习队列（队列也是链表实现的），采用双队列实现（相当于二级索引/二维数组（队列1–第一维，队列2–第二维））：
- 队列2：存储位于长队中的同一组的人
- 队列1：存储位于长队中的组号
数据结构如下：
queue<int> q1, q2[1010]; // 总团队队列，组内部队列
可定义map<int, int> team;存储人x的编号到组别编号，便于查询
注意点
- 每个测试用例后均需一空行，包括最后一个
- 命令判断时注意提取共性，简化代码
- 命令判断时，由于每个命令首字母均不同，因此可直接比较首字母，提高效率
- 由于
map仅用于查询，也可用由哈希算法实现的unordered_map实现 - 若是超时，将
cin/cout全改为scanf/printf
AC代码（C++11，双队列/二级索引/二维数组）
#include<bits/stdc++.h>
using namespace std;
int t, n, x, num=0;
string cmd;
int main() {
while (cin >>t && t != 0) {
map<int, int> team; // 编号x->组别编号
for (int i = 0; i < t; i ++) { // 组别编号
cin >>n;
for (int j = 0; j < n; j ++) { // 每一组
cin >>x;
team[x] = i;
}
}
printf("Scenario #%d\n", ++num); // 输出测试用例编号
queue<int> q1, q2[1010]; // 总团队队列，组内部队列
while (cin >>cmd && cmd[0] != 'S') {
if (cmd[0] == 'E') { // 入队
cin >>x;
if (q2[team[x]].empty()) { // 组内不存在队员
q1.push(team[x]); // 进入总队列
}
q2[team[x]].push(x); // 组内不存在队员，加入总队列最后
}
else if (cmd[0] == 'D') { // 出队
printf("%d\n", q2[q1.front()].front());
q2[q1.front()].pop();
if (q2[q1.front()].empty()) q1.pop(); // 维护总队列
}
}
puts("");
}
return 0;
}