主要的關鍵在于:不要試圖讓所有團隊的人在一個隊列里面,因為這樣如果新入隊的是一個前面團隊的成員則必須先出隊再入隊。
應該把每個團隊看做一個整體,用一個隊列維護團隊的順序,用t個隊列維護每個團隊內部的順序。
還有就是要維護成員編號到團隊的映射關系,我這里用了一個一維數組,因為覺得1e6
也不是很大。看到書里面用的map
,覺得可以但是沒必要。
我還用了一個數組去維護每個團隊是否有人站隊。看書里面的代碼才發現完全是多余的,我們可以通過每個團隊自己的隊列是不是空來判斷。
多組樣例輸入,應該把循環放在主函數里面,然后把初始化、讀入、處理分開。多組樣例的初始化十分重要,很容易出現問題。這里因為初始化不是很復雜我和讀入放在了一起。
感覺自己的代碼結構清晰一點。書里面的命名都好簡潔,覺得自己如果這樣命名很快就忘記是干什么的了。可能還是水平不夠,駕馭不了太復雜的代碼。
還有就是不要忘記關閉同步加速cin/cout
#include <iostream>
#include <string>
#include <array>
#include <queue>using namespace std;namespace {constexpr int MAX_TEAM = 1005;constexpr int MAX_MEM = 1e6 +5;array<int, MAX_MEM> id; //team id of each memberqueue<int> team; //team queuearray<queue<int>, MAX_TEAM> team_member;//member queue in each teamarray<bool, MAX_TEAM> is_in_queue;int t;int case_num = 0;
}void input() {while (!team.empty()) team.pop();int n, x;for (int i = 0; i < t; ++i) {is_in_queue[i] = false;while (!team_member[i].empty()) team_member[i].pop();cin >> n;while (n--) {cin >> x;id[x] = i;}}
}void deal() {string cmd;int x;int team_id;while (cin >> cmd && cmd[0] != 'S') {if (cmd[0] == 'E') {cin >> x;if (is_in_queue[id[x]]) {team_member[id[x]].push(x);} else {team.push(id[x]);is_in_queue[id[x]] = true;team_member[id[x]].push(x);}} else {team_id = team.front();auto &the_team = team_member[team_id];cout << the_team.front() << "\n";the_team.pop();if (the_team.empty()) {team.pop();is_in_queue[team_id] = false;}}}
}int main() {ios::sync_with_stdio(false);while (cin >> t) {if (t == 0) {break;}++case_num;cout << "Scenario #" << case_num << "\n";input();deal();cout << "\n";}return 0;
}