## 資訊之芽 week12 ## 北區作業題解 --- ## 20 - 中國人排隊問題 ---- * 排隊的問題上課有講過可以用：`queue` * 但是他多了一個神奇的條件： * 如果隊伍中已經有了自己的「同夥的」 * 就直接插隊排在自己「同夥的」的後面 * 要怎麼用 `queue` 呢？ ---- ### 觀察 * 在插隊的時候，是插在「同夥的」的後面 * 拿公仔也會是「同夥的」第一個進去的人先拿 * 不覺得這樣的運作方式也很像是某資料結構嗎？ ---- ### 觀察 * 「同夥的」內部運作符合「先進先出」的順序 * 所以可以用 `queue` 來維護「同夥的」的資訊！ ---- ### 觀察 * 「同夥的」內部運作符合「先進先出」的順序 * 所以可以用 `queue` 來維護「同夥的」的資訊！ * 於是我們可以得到一個 `queue` 中 `queue` 的作法 ---- ### 實作 * 因為「同夥的」一定都會排在一起 ---- ### 實作 * 因為「同夥的」一定都會排在一起 * 所以可以開一個紀錄「同夥編號的」`queue`，紀錄現在排在隊伍的 **「同夥的」的團體編號** ---- ### 實作 * 因為「同夥的」一定都會排在一起 * 所以可以開一個紀錄「同夥編號的」`queue`，紀錄現在排在隊伍的 **「同夥的」的團體編號** * 用很多 `queue` 來維護每組「同夥的」內部的資訊 ---- * 因為「同夥的」一定都會排在一起 * 所以可以開一個紀錄「同夥編號的」`queue`，紀錄現在排在隊伍的 **「同夥的」的團體編號** * 用很多 `queue` 來維護每組「同夥的」內部的資訊 * 這樣會有一個記編號的 `queue` * 跟 $N$ 個維護「同夥的」內部資訊的 `queue` ---- ### 實作細節一 * 存「團體編號的」queue：`mainQueue` * 用很多 `queue` 來維護每組「同夥的」內部的資訊 * \> 可以用 `queue` 的陣列！ ```cpp= queue<int> mainQueue; queue<int> que[1005]; ``` ---- ### 實作細節二 * 對於每個人，需要知道他是哪一團的 * \> 開一個很大的陣列 `teams` (大小是人們的編號) * 用 `teams[index]` 來存`index` 這個人是哪一組 ---- ### 實作細節二 * 對於每個人，需要知道他是哪一團的 * \> 開一個很大的陣列 `teams` (大小是人們的編號) * 用 `teams[index]` 來存`index` 這個人是哪一組 * (update) <b style="color:red">有可能有人不在任何一個團體裡面</b> * (update) `teams[index]` 可以存 `-1` 來表示 ---- ### 實作細節三 * 對每個團體，需要知道有沒有「同夥的」在排隊 * \> 開一個陣列 `inQueue` (大小是團體的數量) * 用 `inQueue[team]` 來存同夥編號 `team` 的有沒有人在排隊 ```cpp= bool inQueue[N]; // N 是團體的數量 ``` ---- ### 實作細節四 * (update) 因為有可能有人不在任何團體 * 所以 `mainQueue` 裡面不能只放團體編號 * 可以把 `mainQueue` 內容改成放團體的某個「人」 * 就可以用 `teams` 的陣列取得那個人所屬的團體 * **這樣沒有同夥的人就可以是自己一組** ---- ### 實作順序 1. 讀輸入，順便紀錄 `teams` 陣列 * 也就是每個人是哪一組 2. 處理 ENQUEUE x / DEQUEUE 操作 ---- ### ENQUEUE x 操作 1. 先取得 `x` 在哪一組 (`team = teams[x]`) 2. (update) 先檢查 `team` 是不是 `-1`，如果是的話就直接加到 `mainQueue` (因為他自己一組) 3. 檢查有沒有同夥的在排隊：用 `inQueue[team]` 4. 如果有的話直接插進去 `que[team]` 裡面 5. 沒有的話在 `mainQueue` 新增 `team`，把 `inQueue[team]` 設成 `true`，再讓那個人加到 `que[team]` ---- ### DEQUEUE 操作 1. 用 `mainQueue.front()` 取排最前面的團體編號 2. (update) 先檢查 `team` 是不是 `-1`，如果是的話就直接從 `mainQueue` 移掉就直接結束 3. 把 `que[team]` 的第一個人移除掉 3. 檢查 `que[team]` 還有沒有人在排隊，如果沒有就把 `inQueue[team]` 設成 `false`，並且把 `mainQueue` 第一個團體刪掉 ---- ### pseudo code ```python= int teams[1000000]; queue<int> mainQueue, que[1000]; bool inQueue[1000]; # 輸入 for _ from 1 to T: # 把 mainQueue, que[1000], inQueue, teams 全部設為 0 (初始化) for team_idx from 0 to N-1: person_idx = read() teams[person_idx] = team_idx for i from 0 to M-1: if ENQUEUE: x = read() team = teams[x] if team == -1: # x 自己一組 # 直接在 mainQueue 裡面新增 x # 要記得 continue，不然就會繼續跑下去了 if que[team].empty(): # 沒有「同夥的」在排隊 # mainQueue 新增 x # 把 inQueue[team] 設成 `true` # 再把那個人 (x) 加到 que[team] else: # 把那個人 (x) 加到 que[team] if DEQUEUE: # frontTeam = mainQueue 的第一個隊伍 if frontTeam == -1: # 第一個人自己一組 # 直接輸出 + 從 mainQueue 移除掉即可 # 要記得 continue，不然就會繼續跑下去了 # 移除掉 que[frontTeam] 的第一個人，順便輸出他 if que[frontTeam].empty(): # 沒有人了！ # 把 mainQueue 第一個團體刪掉 # 把 inQueue[frontTeam] 設成 false ``` ---- ### 參考程式碼 (尚未公布) --- ## 1111 - 撲克牌排序問題 ---- * 這題在考「自定義 `sort` 函式的排序方式」 * 可以使用 `sort(a, a + n, compare)`，然後定義 `compare` 這個 function * 還有簡單的字串處理 ---- ### 自定義排序 1. 如果有人是 Joker 先 return 2. 分別取得兩個字串的數字 (字串處理) 3. If 數字不一樣，直接 return 小排到大 4. If 數字一樣，取得花色，return 小排到大 * 有發現花色有按照字典序嗎？ ---- ### 字串處理 * 取得花色可以看第一個位置就好 ---- ### 字串處理 * 取得數字可以用字串的「長度」作輔助 * Joker 長度一定是 $1$ * 數字「$10$」長度一定是 $3$ * 其他長度都是 $2$ * 特判 $A,J,Q,K$ 這四個符號 * 剩下的就可以直接用數字得到結果了 ---- ### pseudo code ```cpp= string cards[1000]; int get_value(string s) { // TODO: 實作拿到數字的函式 int size = s.size(); // ... } bool compare(string a, string b) { if a 或 b 是 joker: // return something // 拿到數字 int val_a = get_value(a), val_b = get_value(b); if val_a != val_b: // 不同數字 // return something // 同數字，不同花色 // return something } int main() { // 輸入 n // 輸入 cards sort(cards, cards + n, compare); // 輸出 cards } ``` ----