UVA 540团队队列（STL之队列、优先队列）

218 阅读 0 评论 144 点赞

我是靠谱客的博主无心自行车，这篇文章主要介绍UVA 540团队队列（STL之队列、优先队列），现在分享给大家，希望可以做个参考。

题目描述

有t个团队的人正在排一个长队。每次新来一个人时，他进入队伍的顺序有两种选择：如果有队友在长队中，则他排队长队中最后一个队友的后面；如果没有队友在长队中，则他排到整个长队的最后面。
要求该程序有三种指令：

ENQUEUE x：编号为x的人进入长队；
DEQUEUE x：长度的队首出队
STOP：停止本次case

题目分析

维护两个队列queue，第一个队列是队伍号的队列，第二个队列是所有队伍中各自队员的队列；
根据操作依次进行操作即可

AC代码

复制代码

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
/*
Author:snnu_lgw
Date：2020/6/26
uva 540 
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t,Case=0;
	map<int,int>team;//映射关系为（每个人的编号，每个人的队伍的编号）
	while(cin>>t&&t!=0)
	{
		printf("Scenario #%dn",++Case);
		for(int i=0;i<t;i++)
		{
			int n,x;
			cin>>n;    //该队伍的人数 
			while(n--)
			{
				cin>>x;  //输入某个人的编号
				team[x] = i; //他们的队伍号都为i 
			}
		}
		
		queue<int> q,q2[1000+10];//q是队伍编号的队列，q2是每个队伍的队列 
		while(true)
		{
			string str;
			cin>>str;
			if(str[0]=='E')
				{
					int num;
					cin>>num;
					int t = team[num]; //编号为num的人的队伍号
					if(q2[t].empty())	
						q.push(t);    //团队t进入到团队队列 
					q2[t].push(num);   //num进入到队伍t的队列中 
				}
			else if(str[0]=='D')
				{
					int top = q.front(); //队伍编号 
					printf("%dn",q2[top].front());//输出该队伍中的第一个人的编号
					q2[top].pop(); //同时把这第一个人弹出队列
					if(q2[top].empty())//如果把这个人弹出队列后，队伍为空，那么需要把这个队伍从团体队列中删除
						q.pop(); 
				}
			else if(str[0]=='S')
				break;
		}
		cout<<endl;
	}
	return 0;
}

补充知识

优先队列，弹出队列时默认弹出优先级高的！

复制代码

1
2
3
4
5
6
7
8
9
10
11
/*默认越小的整数，优先级越低，*/
priority_queue<int>pq;

/*重新定义，越大的整数优先级越低*/
priority_queue<int,vector<int>,greater<int> >pq;
/*
**  优先队列(大顶堆),加上两个参数之后变为小顶堆，注意在第三个参数后面加一个空格，否则视为输入流信号 
**  实现哈夫曼树，每次可以将队列中优先级最大(数值最小)的那个出队列。哈夫曼树的权值即为所以非叶子节点的和 
*/