算法1:stl-queue维护(暴力枚举) $O(n)$
//维护每个小组内的顺序,1000个队列;循环小组间的顺序;1个队列
//用数组标记该编号小朋友属于那个组别;
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e6+10;
int tid[M], n; //标记编号属于那个小组
int main() {
int c = 0;
while (scanf("%d", &n), n) {
printf("Scenario #%d\n", ++c);
for (int i = 0; i < n; ++ i) { //n个小组
int cnt, x;
scanf("%d", &cnt); //小组的人数
while (cnt--) {
scanf("%d", &x);
tid[x] = i; //编号x的人属于第i组 怎么知道每个人属于那个小组
}
}
//维护出队列
queue<int> preson[N]; //组内队列
queue<int> team; //组间队列
char op[25], ed[25] = "STOP";
int x;
while (scanf("%s", op), strcmp(op, "STOP")) {
if (strcmp(op, "ENQUEUE") == 0) {
scanf("%d", &x);
int id = tid[x]; //获取属于的小组编号
if (preson[id].empty()) team.push(id); //小组第一个,加入到team队列中
preson[id].push(x);
} else {
int id = team.front(); //拿到team的队头 小组编号
auto &q = preson[id]; //获取维护该小组的 组内的队列
printf("%d\n", q.front()); //输出该队列的第一个
q.pop(); //删除第一个
if (q.empty()) team.pop(); //出队后,组内队列空了,从team中删除
}
}
printf("\n");
}
return 0;
}
算法2:数组模拟队列() $O(n)$
//数组模拟队列
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e6+10;
int tid[M];
int q[N][N], hh[N], tt[N]; //hh[x] tt[x] 表示第x个队列的头指针和尾指针
int main() {
int c = 0, n;
while (scanf("%d", &n), n) {
printf("Scenario #%d\n", ++c);
for (int i = 0; i < N; ++ i) { //初始化队列的队头和队尾
hh[i] = 1;
tt[i] = 0;
}
for (int i = 1, x, cnt; i <= n; ++ i) { //小组编号从1开始,0是维护组间队列的
scanf("%d", &cnt);
while (cnt--) {
scanf("%d", &x);
tid[x] = i; //记录x在第i组
}
}
char op[35];
int x;
while (scanf("%s", op), op[0] != 'S') {
if (op[0] == 'E') {
scanf("%d", &x);
int id = tid[x];
if (hh[id] > tt[id]) q[0][++tt[0]] = id; //小组队列为空,是小组第一人
q[id][++tt[id]] = x;
} else {
int id = q[0][hh[0]]; //获取组间队列的队头组号
if (hh[id] <= tt[id]) printf("%d\n", q[id][hh[id]++]);
if (hh[id] > tt[id]) hh[0]++;
}
}
printf("\n");
}
return 0;
}