同題：UVa 00540 – Team Queue
「Queues」和「Priority Queues」是大部份的人都知道的資料結構。
然而，儘管「Team Queue」在日常生活中經常發生，但並不是眾所周知。
在「Team Queue」中，每個元素都屬於一個 Team。如果某個元素進入 Queue，它將首先從頭到尾搜索 Queue，以檢查其 teammates (同一 Team 的元素) 是否已經在 Queue 中。
如果是，它將排在其Team的最後一個。如果不是，它將排在 Queue 最後面。
Dequeuing 的方式與普通 Queue 中一樣：元素按照在 Team Queue 中出現的順序從頭到尾進行處理。
您的任務是寫一個程式模擬 Team Queue。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| EOF 輸入，每組測資第一行為一個整數 T (1 ≤ T ≤ 1000)，T 代表有幾個 Team。 如果 T = 0 代表輸入結束。 接下來 T 行，每行第一個整數 N (1 ≤ N ≤ 1000)，代表該 Team 的成員數量。 之後跟著 N 個整數 Xi (0 ≤ Xi ≤ 999999)。 接下來為若干個指令，以下為指令列表： ENQUEUE X: 若 X 所屬的團隊成員已在Queue內，就排進 Team 內的最後一個。若沒有，則排進 Queue 的最後一個。 DEQUEUE: 將Queue 最前面的元素移除，並輸出此元素。 STOP: 結束。 注意：實現的 Team Queue 需有效率，元素的 Enqueing 和 Dequeuing 都應僅花費恆定的時間。 | 對於每組測資，輸出「Scenario #k」，其中 k 是測資的編號。 接著對於每個「DEQUEUE」指令，將已出 Queue 的元素輸出。 在每組測資之後皆要輸出空白行。 |
| 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 2 5 259001 259002 259003 259004 259005 6 260001 260002 260003 260004 260005 260006 ENQUEUE 259001 ENQUEUE 260001 ENQUEUE 259002 ENQUEUE 259003 ENQUEUE 259004 ENQUEUE 259005 DEQUEUE DEQUEUE ENQUEUE 260002 ENQUEUE 260003 DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP 0 | Scenario #1 101 102 103 201 202 203 Scenario #2 259001 259002 259003 259004 259005 260001 |
解題思路
宣告一個 map<string, int> 來存每一個編號的隊伍是哪個，Team Queue 可以使用一個二維陣列來實現。
需要宣告一個 map<int, int> 來存目前每一個隊伍在二維陣列中的位置，如果進行 ENQUEUE 的時候該隊伍的值為 0，則將一個新的一維陣列包含字串 Push_Back 到二維陣列中，並且將該隊伍的 map 值設定為二維陣列的大小也就是最後面。
進行 DEQUEUE 時就將二維陣列的 [0][0] 輸出並且將其刪除，每次刪除都要判斷第一個一維陣列還有沒有資料，如果沒有的話就將這個一維陣列刪除，並且要更新 Map 中的所有資料，可以使用 for(auto it:Map) 來更新資料。如果 it.second == 1 就代表這是剛剛刪掉的一維陣列，將其設為 0，如果不是 1 也不是 0 就將 Map 值 -1。
範例程式碼－ZeroJudge E564: Team Queue
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int T, count = 1;
while (cin >> T && T != 0) {
map<string, int>MAP;
for (int i = 0; i<T; i++) {
int N;
cin >> N;
for (int j = 0; j<N; j++) {
string str;
cin >> str;
MAP[str] = i;
}
}
string str;
vector<vector<string>>v;
map<int, int>hi;
cout << "Scenario #" << count << "\n";
count++;
while (cin >> str && str != "STOP") {
if (str == "ENQUEUE") {
string s;
cin >> s;
int index = hi[MAP[s]];
if (index == 0) {
vector<string>tmp;
tmp.push_back(s);
v.push_back(tmp);
hi[MAP[s]] = v.size();
}
else v[index-1].push_back(s);
continue;
}
cout << v[0][0] << "\n";
v[0].erase(v[0].begin());
if (v[0].empty()) {
v.erase(v.begin());
for (auto it:hi) {
if (it.second == 1) hi[it.first] = 0;
else if (it.second != 0) hi[it.first]--;
}
}
}
cout << "\n";
}
}
//ZeroJudge E564
//Dr. SeanXD