Poj2259（团体队列）

80 阅读 0 评论 53 点赞

我是靠谱客的博主欣慰季节，最近开发中收集的这篇文章主要介绍Poj2259（团体队列），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意
有t个团队的人排队，每有一个新来的人时，如果他有队友正在排队，那么他就会站在他队友的后面。如果没有队友，就站在队伍的最后面。
输入每个团队中所有队员的编号，要求支持如下3中指令：
ENQUEUE x：编号为x的人进入长队；
DEQUEUE：长队的队首出队；
STOP：停止模拟。
对于每个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

最开始队伍是空的，然后，一号团的101号大妈来了。
（此时，队伍顺序为：101.）
接着二号团201大爷也跟了过来。
（此时，队伍顺序为：101，201.）
接着，一号团的102号大妈也来了，不把二号团的大爷放眼里，站在了201号大爷前面。
（此时，队伍顺序为：101，102，201.）
二号团202号大爷见状，不好吭声，只好紧接在201号大爷之后。
（此时，队伍顺序为：101，102，201，202）
一号团又来一103号大姐，不把二团放眼里般站在了一团之后。
（此时，队伍顺序为：101，102，103，201，202）
二团最后203号大爷不急不慢走到了队尾。
（此时，队伍顺序为：101，102，103，201，202，203）

从样例和生活常识综合分析可得：无论后面来的人是谁，都可以插入到自己的团队内排在后面。
所以可以简单找到做题突破口：将每个团体当成一个个体进行排队，然后再队每个团队内部进行一次排队。

那么！用什么方法呢？

answer：都说了是排队了，那~~TMD~~ 肯定是用队列了啊！

队列是啥？在这里插入图片描述
那么队列怎么写呢？
answer：用STL啊！

STL大法吼啊！！！吼啊！！!

因为题目给了每个人的编号是<=999999的，所以，我用了类似桶排的方法记录了每个人所在队伍。
即：

int a[10000000];
for(int i = 0;i < n;++ i){
	scanf("%d",&hhh);
	for(int j = 0;j < hhh;++ j){
		scanf("%d",&x);
		a[x] = i;
	}
}

然后剩下的就只用对操作进行简单的模拟就好了！
下面附上完整代码！

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring> 
#include <queue>
using namespace std;
int n;
queue<int> Q;
queue<int> q[1006];
char ch[30];
int a[10000000];
int x;
int f;
int k = 1;
int main(void){
	while(scanf("%d",&n)){
		if(n == 0)//结束标志，跳出循环
			break;
		cout << "Scenario #" << k<<endl;	
		k ++;
		memset(a,0,sizeof(a));
		for(int i = 1;i <= 1005;++ i){
			while(!q[i].empty())
				q[i].pop();
		}
			
		while(!Q.empty())
			Q.pop();
		int hhh;
		for(int i = 0;i < n;++ i){
			scanf("%d",&hhh);
			for(int j = 0;j < hhh;++ j){
				scanf("%d",&x);
				a[x] = i;
			}
		}//while开始到这里都是在初始化，因为有多组数据
		while(scanf("%s",&ch)){
			if(ch[0] == 'S')
				break;
			if(ch[0] == 'E'){
				scanf("%d",&x);
				if(q[a[x]].empty()){
					Q.push(x);
					q[a[x]].push(x);
				}//某个团队第一个人入队的情况。
				else{
					q[a[x]].push(x);//有队友直接插队！
				}
			}
			if(ch[0] == 'D'){
				printf("%dn",q[a[Q.front()]].front());
				q[a[Q.front()]].pop();//出队！！！
				if(q[a[Q.front()]].empty())//这个团队走完了。
					Q.pop();
			}
		}
		cout << endl;
	}
	
	return 0;
}

码风较丑，请勿嘲笑。