UVA 540 Team Queue

1
2
3
4
5
有t个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友身后。如果没有任何一个队友排队，则他会排到长队的队尾。输入每个团队中所有队员的编号，要求支持如下3种指令（前两种指令可以穿插进行）。
ENQUEUE：编号为X的人进入长队。
DEQUEUE：长队队首出队。
STOP：停止模拟。
对于每个DEQUEUE指令，输出出队的人的编号。

1
2
3
4
5
6
输入文件中有一组或多组测试数据。
每组测试数据开始有t个团队。下面t行，每行的第一个数字代表这个团队人数，后面是这几个人的编号。编号为0到999999之间的一个整数。
每组测试数据以“STOP”结束。
输入以t==0时结束。
警告：一个测试用例可能包含最多200000（二十万）个命令，所以实现
团队的队列应该是有效的。

1
对于每组测试数据，先打印一句"Scenario #k"，k是第几组数据。对于每一个"DEQUEUE"指令，输出一个出队的人的编号。每组测试数据后要换行，即使是最后一组测试数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001

1
队列，具体请看代码，参考紫书

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
复制代码#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
const int maxn = 1005;
int main() {
	int N, Case = 0;
	while(~scanf("%d",&N) && N) {
		printf("Scenario #%dn",++Case);
		map<int ,int> team;
		while(N--) {
			int n, x;
			scanf("%d",&n);
		for(int i = 0; i < n; i++) {
				scanf("%d",&x);
				team[x] = N;//把每个人都进行标记，代表哪一支队伍
			}
		}
		string op;
		queue<int> q, q2[maxn];
		while(1) {
			int x;
			cin >> op;
			if(op[0] == 'S') break;
			else if(op[0] == 'D') {
				int t = q.front();//先找到这个人属于哪一组
				printf("%dn",q2[t].front());//然后根据弹出每一组的第一个人
				q2[t].pop();
				if(q2[t].empty()) q.pop();
			}
			else if(op[0] == 'E') {
				scanf("%d",&x);
				int t = team[x];
				if(q2[t].empty()) q.push(t);//压入
				q2[t].push(x);
			}
		}
		printf("n");
	}
	return 0;
}
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
const int maxn = 1005;
int main() {
	int N, Case = 0;
	while(~scanf("%d",&N) && N) {
		printf("Scenario #%dn",++Case);
		map<int ,int> team;
		while(N--) {
			int n, x;
			scanf("%d",&n);
		for(int i = 0; i < n; i++) {
				scanf("%d",&x);
				team[x] = N;//把每个人都进行标记，代表哪一支队伍
			}
		}
		string op;
		queue<int> q, q2[maxn];
		while(1) {
			int x;
			cin >> op;
			if(op[0] == 'S') break;
			else if(op[0] == 'D') {
				int t = q.front();//先找到这个人属于哪一组
				printf("%dn",q2[t].front());//然后根据弹出每一组的第一个人
				q2[t].pop();
				if(q2[t].empty()) q.pop();
			}
			else if(op[0] == 'E') {
				scanf("%d",&x);
				int t = team[x];
				if(q2[t].empty()) q.push(t);//压入
				q2[t].push(x);
			}
		}
		printf("n");
	}
	return 0;
}