• 排隊的問題上課有講過可以用：queue

• 但是他多了一個神奇的條件：

• 如果隊伍中已經有了自己的「同夥的」

• 就直接插隊排在自己「同夥的」的後面

• 要怎麼用 queue 呢？

觀察

• 在插隊的時候，是插在「同夥的」的後面

• 拿公仔也會是「同夥的」第一個進去的人先拿

• 不覺得這樣的運作方式也很像是某資料結構嗎？

觀察

• 「同夥的」內部運作符合「先進先出」的順序

• 所以可以用 queue 來維護「同夥的」的資訊！

觀察

• 「同夥的」內部運作符合「先進先出」的順序

• 所以可以用 queue 來維護「同夥的」的資訊！

• 於是我們可以得到一個 queue 中 queue 的作法

實作

• 因為「同夥的」一定都會排在一起

實作

• 因為「同夥的」一定都會排在一起

• 所以可以開一個紀錄「同夥編號的」queue，紀錄現在排在隊伍的 「同夥的」的團體編號

實作

• 因為「同夥的」一定都會排在一起

• 所以可以開一個紀錄「同夥編號的」queue，紀錄現在排在隊伍的 「同夥的」的團體編號

• 用很多 queue 來維護每組「同夥的」內部的資訊

• 因為「同夥的」一定都會排在一起

• 所以可以開一個紀錄「同夥編號的」queue，紀錄現在排在隊伍的 「同夥的」的團體編號

• 用很多 queue 來維護每組「同夥的」內部的資訊

• 這樣會有一個記編號的 queue

• 跟 \(N\) 個維護「同夥的」內部資訊的 queue

實作細節一

• 存「團體編號的」queue：mainQueue

• 用很多 queue 來維護每組「同夥的」內部的資訊

• > 可以用 queue 的陣列！

queue<int> mainQueue;
queue<int> que[1005];

實作細節二

• 對於每個人，需要知道他是哪一團的

• > 開一個很大的陣列 teams (大小是人們的編號)

• 用 teams[index] 來存index 這個人是哪一組

實作細節二

• 對於每個人，需要知道他是哪一團的

• > 開一個很大的陣列 teams (大小是人們的編號)

• 用 teams[index] 來存index 這個人是哪一組

• (update) 有可能有人不在任何一個團體裡面

• (update) teams[index] 可以存 -1 來表示

實作細節三

• 對每個團體，需要知道有沒有「同夥的」在排隊

• > 開一個陣列 inQueue (大小是團體的數量)

• 用 inQueue[team] 來存同夥編號 team 的有沒有人在排隊

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] 的第一個人移除掉

4. 檢查 que[team] 還有沒有人在排隊，如果沒有就把 inQueue[team] 設成 false，並且把 mainQueue 第一個團體刪掉

pseudo code

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
                

參考程式碼

(尚未公布)

• 這題在考「自定義 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

 
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
}