UVA - 540-Team Queue解题报告（stl+模拟）题目概述思路分析完整代码

77 阅读 0 评论 51 点赞

我是靠谱客的博主老实水杯，最近开发中收集的这篇文章主要介绍UVA - 540-Team Queue解题报告（stl+模拟）题目概述思路分析完整代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目概述

链接：https://vjudge.net/problem/UVA-540
有t个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友身后。如果没有任何一个队友排队，则他会排到长队的队尾。输入每个团队中所有队员的编号，要求支持如下3种指令（前两种指令可以穿插进行）。
ENQUEUE：编号为X的人进入长队。
DEQUEUE：长队队首出队。
STOP：停止模拟。
对于每个DEQUEUE指令，输出出队的人的编号。
输入描述：
输入文件中有一组或多组测试数据。
每组测试数据开始有t个团队。下面t行，每行的第一个数字代表这个团队人数，后面是这几个人的编号。编号为0到999999之间的一个整数。
每组测试数据以“STOP”结束。
输入以t==0时结束。
警告：一个测试用例可能包含最多200000（二十万）个命令，所以实现
团队的队列应该是有效的。
输出描述：
对于每组测试数据，先打印一句"Scenario #k"，k是第几组数据。对于每一个"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

思路分析

这道题目标是很明确的，但是一个问题就是在于怎么存储、处理这些数据。我一开始想着用queue去包含一个结构体，结构体再包含一个vector来存储，但是后来发现层数太多，操作起来很麻烦。。所以，就放弃了。
后来，我想到了一个比较好的解决方法：
因为入队后队伍间的顺序就不再改变。所以，可以用一个queue，通过存储int型数据来保存队伍顺序。然后，每个队伍再分别用一个vector来存储现在在队内的队员。这时候，还需要一个map，把queue里的数据和vector联系起来。这就是到stl的综合应用题了。

完整代码


#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	#ifdef LOCAL
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	map<int,int> list;//人员名单
	map<int,vector<int>> now;//队号-现在在队人 
	queue<int> que;
	int n;
	int kase=1;
	while(cin>>n&&n!=0)
	{
		map<int,int> list;//人员名单
		map<int,vector<int>> now;//队号-现在在队人 
		queue<int> que;
		printf("Scenario #%dn",kase++);
		int k=1;
		while(n--)
		{
			int t;
			cin>>t;
			while(t--)
			{
				int m;
				cin>>m;
				list[m]=k;
			}
			k++;
		}
		string cmd;
		while(cin>>cmd&&cmd!="STOP")
		{
			if(cmd=="ENQUEUE")
			{
				int p;
				cin>>p;
				if(now[list[p]].empty())
				{
					que.push(list[p]);
					now[list[p]].push_back(p);
				}
				else
				{
					now[list[p]].push_back(p);
				}
			}
			if(cmd=="DEQUEUE")
			{
				int num=que.front();
				cout<<*now[num].begin()<<"n";
				now[num].erase(now[num].begin());
				if(now[num].empty()) que.pop();
			}
		}
		cout<<endl;
		
	}
	return 0;
}//