UVA540 Team Queue 解题报告

UVA540 Team Queue 解题报告

题目链接

https://vjudge.net/problem/UVA-540

题目大意

有t个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友的身后。如果没有任何一个队友排队，则他会排到长队的队尾。输入每个团队中所有队员的编号，要求支持如下3种指令（前两种指令可以穿插进行）。

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

对于每个DEQUEUE指令，输出出队的人的编号

解题思路

每个团队可以建模为一个队列，而团队整体又形成一个队列。queue teamQue为团队的队列，记录团队整体的先后顺序，存放的是每个团队的编号，queue q[]存放的是各自团队成员的队列，q[i]代表的是团队i的成员队列。具体实现见代码和注释。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;void solve() {int t, Case = 0;while (cin >> t, t != 0) {cout << "Scenario #" << ++Case << endl;// 记录每个人的团队编号map<int, int> team;for (int i = 0; i < t; i++) {int n, x;cin >> n;while (n--) {cin >> x;team[x] = i;}}// 模拟排队插队queue<int> teamQue, q[maxn];  // teamQue为团队的队列，q[i]为第i个团队的成员队列while (true) {string s;cin >> s;if (s[0] == 'S')break;if (s[0] == 'D') {int tid = teamQue.front();int x = q[tid].front();q[tid].pop();cout << x << endl;if (q[tid].empty()) {teamQue.pop();}} else if (s[0] == 'E') {int x;cin >> x;int tid = team[x];if (q[tid].empty()) {teamQue.push(tid);}q[tid].push(x);}}cout << endl;}}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);solve();return 0;
}