解题报告——例题 5-6团体队列(Team Queue UVa 540)——31行代码解决

125 阅读 0 评论 83 点赞

我是靠谱客的博主单纯含羞草，这篇文章主要介绍解题报告——例题 5-6团体队列(Team Queue UVa 540)——31行代码解决，现在分享给大家，希望可以做个参考。

题目大意：

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

样例输入：

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

样例输出：

Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001

本题的难点：

难点1：如何判断新进队的队员是哪个团队的，
难点2：判断出ta是哪个团队的后，判断该团队最后一个人在哪。

解决办法：

1、利用map的映射关系建立一个索引。 key值是每个团队的编号，value是该团队下队员的编号，key对value是一对多的关系。
2、建立队列q，二维队列q2(相当于很多行队列)，q存储团队编号， q2[i]存储编号为i的团队下队员的编号。
这样一来，如果是入队：对新进队员判断时, 若新队员编号为i，则map[i]就是团队的编号，只需将新队员入队q2[map[i]]中即可（该团队最后一个位置）。
如果是出队：则q.top()为队列头部团队， q2[q.top()].pop()表示将最靠前团队中最前面的队员出队。

核心思想：

利用map的映射特性做二维队列的索引

代码：

复制代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxt = 1000 + 10;				//防止溢出 
int main() {
	int t, kase = 0;
	while(cin >> t && t) {			//t个团队 
		cout << "Scenario #" << ++kase << endl;
		map<int, int> team;			//key是团队编号，value是个人编号 
		for(int i = 0; i < t; i++) {//输入每个团队队员编号 
			int n, x; cin >> n;
			while(n--) { cin >> x; team[x] = i; }	//建立索引 
		}
		queue<int> q, q2[maxt];		//q是团队队列，q2[i]是团队i成员的队列
		for(;;) {
			int x;
			char cmd[10];  cin >> cmd;
			if(cmd[0] == 'S') break;
			else if(cmd[0] == 'D') {
				int t = q.front();
				cout << q2[t].front() << endl; q2[t].pop(); 
				if(q2[t].empty()) q.pop();		//团体t全体出队列 
			} else if(cmd[0] == 'E') {
				cin >> x;
				int t = team[x];
				if(q2[t].empty()) q.push(t);	//团队t进入队列
				q2[t].push(x); 
			} 
		}  
		cout << endl; }
	return 0;
}