Team Queue UVA - 540 团体队列

110 阅读 0 评论 73 点赞

我是靠谱客的博主神勇秋天，这篇文章主要介绍Team Queue UVA - 540 团体队列，现在分享给大家，希望可以做个参考。

题目链接

有t个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友的身后。如果没有任何一个队友排队，则他会排到长队的队尾。输入每个团队中所有队员的编号，要求支持如下3种指令（前两种指令可以穿插进行）。

ENQUEUEx：编号为x的人进入长队。
DEQUEUE：长队的队首出队。
STOP：停止模拟。

对于每个DEQUEUE指令，输出出队的人的编号。
【分析】
本题有两个队列：每个团队有一个队列，而团队整体又形成一个队列。例如，有3个团队1，2，3，队员集合分别为{101，102，103，104}、{201，202}和{301，302，303}，当前长队为{301，303，103，101，102，201}，则3个团队的队列分别为{103，101，102}、{201}和{301，303}，团队整体的队列为{3，1，2}。代码如下：

复制代码

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
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int N = 1000+5;

int main(int argc, char** argv) {
	int t, kase = 0;	
	while( scanf("%d",&t) == 1 && t){
		printf("Scenario #%dn", ++kase);
		map<int,int> team;	
		queue<int> q, q2[N];
		for(int i = 1; i <= t; i++){
			while(!q2[i].empty())  q2[i].pop();
			int n, x;
			scanf("%d",&n);
			while(n--){
				scanf("%d",&x);
				team[x] = i;
			}
		}
		char opt[10];				
		while( scanf("%s",opt) == 1 && opt[0] != 'S'){
			if( opt[0] == 'E'){
				int x;
				scanf("%d",&x);
				int idx = team[x];
				if(q2[idx].empty()) q.push(idx);// 团队idx进入队列						
				q2[idx].push(x);					
			}else if(opt[0] == 'D'){
				int idx = q.front();
				printf("%dn",q2[idx].front()); q2[idx].pop();
				if(q2[idx].empty()) q.pop();
			}
		}
		printf("n");
	}
	return 0;
}