【UVA-540】解题报告（STL，queue，模拟）

原始题目

题目大意

团队队列，给定n个团队每个团队的人员，对于一个整体队列，有入队出队两种操作。

  • 入队：如果长队列中有将要入队成员的同团队成员，则该成员插入到同团队成员的最后方，如果没有，则插入整个队伍最后方。
  • 出队：整体队列的队首人员出列。

解题思路

  • 先map到自己的团队号。
  • 建立不同团队的人员队列和团队队列（储存团队号），入队操作时检查本团队的人员队列是否为空，如果为空。 那么就在团队队列插入该成员的团队号，然后本队队列入队该成员。不为空的话只在本队队列入队即可。出队操作检查出队成员所在本队 队列是否为空，为空就在团队队列中也出队队伍号。

解题代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <string>
#include <sstream>
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i);
#define ms(x,a) memset((x),a,sizeof((x))) 
#define all(x) x.begin(),x.end()
#define ins(x) inserter(x,x.begin()) 
#define INF 0x3f3f3f3f
#define eps 1e-8
#define fi first
#define e 2.718281828459045235360287471352662497757247093699959574966967627724076630353 
#define se second
#define mp make_pair
#define pb push_back
#define np next_permutation
#define gapline cout<<"##======================##"<<endl
using namespace std;
const int maxn=1e3+5;
const int maxl=26;
const int maxm=1e5+5;
typedef long long ll;
typedef unsigned long long ull;

//团体队列  一个q储存团体序号， q2[i]表示i团体内的队列 
// 出队时  q2[q[front]] 为空时 q.pop();
// 入队时  q2[mp[number]]非空时直接插队尾，  空时  插队尾同时q.push(mp[number]) 
int t,n,kase;
map<int,int> mmp;
int main(){
	ios::sync_with_stdio(false);
	while(cin>>t&&t){
		cout<<"Scenario #"<<++kase<<endl;
		mmp.clear();
		int x;
		rep(i,0,t){
			cin>>n;
			rep(j,0,n){
				cin>>x;
				mmp[x]=i;
			}
		}
		queue<int> q,q2[maxn];
		//q为团队队列   q2[i] 为i团队队内队列
		string c;
		while(cin>>c && c[0]!='S'){
			if(c[0]=='E'){
				cin>>x;
				int id=mmp[x];
				if(q2[id].empty()){
					q.push(id);
				}
				q2[id].push(x);
			}
			else{
				int num=q2[q.front()].front();
				cout<<num<<endl;
				q2[q.front()].pop();
				if(q2[q.front()].empty()) q.pop();
			}
		} 
		cout<<endl;
	}
}

收获与反思

合理利用已有的数据结构