团体队列（UVa 540）

ゞ浴缸里的玫瑰 2022-05-17 22:37 152阅读 0赞

**考察点**：map和queue的使用。  
原题链接：

> [https://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=481][https_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_481]  
> 题意：  
> 有t个团队的人在排一个长队。每次新来一个人时，如果有队友排队，则新人会插到最后一个队友的身后。如果没有一个队友排队，则他会排到长队的队尾。  
> 输入每个团队的所有队员的编号，要求支持如下三种指令（前两种可以穿插进行）。

1.  ENQUEUE x：编号为x的人进入长队
2.  DEQUEUE x：长队的队首出队
3.  STOP ：停止模拟。

**题目分析：**  
涉及到队员编号和团队编号，故可以采用`map<int,int>`完成队员编号到所在团队编号的映射。采用两个队列来完成模拟即可。

**代码如下：**

#include<cstdio>
    #include<queue>
    #include<map>
    #include<iostream> 
    using namespace std;
    const int maxn=1010;
    int main(){ 
    	int t,kase=0;
    	while(~scanf("%d",&t)&&t){ 
    		printf("Scenario #%d\n",++kase);
    		
    		//记录所有人的团队编号
    		map<int,int> team;           //team[x]表示编号为x的人所在团队的编号
    		for(int i=0;i<t;i++) { 
    			int n,x;
    			scanf("%d",&n);
    			while(n--){ 
    				scanf("%d",&x);team[x]=i;
    // printf("%d\n",team[x]) ;
    			}
    		}
    		
    //模拟
    //q存放队伍，q2存放按序排列的所有队伍及队伍下的编号 
    queue<int> q,q2[maxn];      //q是团队的队列，q2[i]是团队i成员的队列
     for(; ;){ 
     	int x;
     	char s[10];
     	cin>>s;
     	if(s[0]=='S') break;
    	 else if(s[0]=='D'){ 
    	 	int t=q.front();               //变量t表示团队整体队列的队首 
    	 	printf("%d\n",t);
    	 	printf("%d\n",q2[t].front());  q2[t].pop();	//输出当前队首队伍的第一个人，并将此人出队列 
    	 	if(q2[t].empty()) q.pop();       //团体t全部出队列 
    	 }
    	 else if(s[0]=='E'){ 
     		 scanf("%d",&x);
     		int t=team[x];					//通过map映射找到x的队列序号 
     		if(q2[t].empty()) q.push(t);    //若该队没有排在队伍中，团队t进入队列（队尾） 
    		 q2[t].push(x);					//否则把该队列的人插入到q2的该队中 
    	 } 
     }
    		printf("\n");
    	}
    	return 0;
    }

[https_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_481]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=481