---
# System prepended metadata

title: 0-22 priority_queue
tags: [演算法, C++, APCS, Python]

---

# 0-22 priority_queue

講義不是我寫的，網址在此 https://emanlaicepsa.github.io/2020/10/21/0-index/
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年10月9日

## [TIOJ: 1161. 4.虛擬番茄online](https://tioj.ck.tp.edu.tw/problems/1161)

本題在〈[0-20 set](https://hackmd.io/@yizhewang/ryxv_Axyyl)〉有出現過，當時是用 Python 的 bisect 函式庫及 C++ 的 set 解題，因為是要儲存資料中的3個最小值，也可以使用 priority queue 解題。

### Python 程式碼

無法通過測試，第4筆測資超過記憶體上限。
```python=
import heapq as hq

T = int(input())  # 測試資料組數
for _ in range(T):
    s = []  # 儲存目前需要的能力值，用 heapq，預設由小到大排序，資料要加上負號
    n, k = map(int, input().split())  # 可以學的技能總數 n，要學的技能總數 k
    sa = []  # 學習各技能需要的能力值 s、a
    for _ in range(n): sa.append(list(map(int, input().split())))  # 讀取資料給 sa
    sa.sort()  # 由小到大排序
    ans = 1000000001  # 答案先預設為很大的值
    for i in range(n):  # 依序讀取 sa 的資料
        hq.heappush(s, -sa[i][1])  # 於 s 插入 -sa[i][1] 並保持順序
        if len(s) > k: hq.heappop(s)  # 如果 s 的數量大於 k，移除量值最大的資料
        if len(s) == k:  # 如果 s 的數量等於 k，更新 ans 為 ans 及 sa[i][0] - s[0] 較小值
             ans = min(ans, sa[i][0] - s[0])
    print(ans)
```

### C++ 程式碼

執行時間最久約為 370 ms，使用記憶體最多約為 13052 kB，通過測試。執行速度比 multiset 快很多。
```cpp=
#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;  // 測試資料組數
    for(int i=0; i<T; i++) {
        priority_queue<int> s;  // 儲存目前需要的能力值，由大到小排序
        int n, k; cin >> n >> k;  // 可以學的技能總數 n，要學的技能總數 k
        pair<int, int> sa[n];  // 學習各技能需要的能力值 s、a
        for(int i=0; i<n; i++) cin >> sa[i].first >> sa[i].second;  // 讀取資料給 sa
        sort(sa, sa+n);  // 由小到大排序
        int ans = 1000000001;  // 答案先預設為很大的值
        for(int i=0; i<n; i++) {  // 依序讀取 sa 的資料
            s.push(sa[i].second);  // 於 s 插入 sa[i].second 並保持順序
            if (s.size() > (size_t)k) s.pop();  // 如果 s 的數量大於 k，移除第一項
            if (s.size() == (size_t)k)  // 如果 s 的數量等於 k，更新 ans 為 ans 及 sa[i].first + s.top() 較小值
                 ans = min(ans, sa[i].first + s.top());
        }
        cout << ans << "\n";
    }
    return 0;
}
```

## [TIOJ: 1231 . 寵物雞問題](https://tioj.ck.tp.edu.tw/problems/1231)

### Python 程式碼

第5筆測資會遇到 Runtime Error。
```python=
import heapq as hq

n = int(input())  # 食物數量 n
food = []  # 食物的 (保存期限, 熱量)
for _ in range(n):  # 讀取 n 行資料
    h, d = map(int, input().split())  # 熱量 h，保存期限 d
    food.append((d, h))  # 將 (d, h) 加入 food

food.sort(reverse=True)  # 由大到小排序
k = int(input())  # 結束時間 k
ans = 0  # 答案
idx = 0  # 由 food 讀取資料用的索引值
t = k  # 時刻 t 預設為 k
pq = []  # 儲存目前未過期的食物熱量，為了將量值由大到小排序，要加負號

while t > 0:  # t > 0 繼續執行 
    while idx < n and food[idx][0] >= t:  # 如果 idx 還沒有出界而且 food[idx] 還沒有過期
        hq.heappush(pq, -food[idx][1])  # 將 -food[idx][1] 加入 pq
        idx += 1  # idx 加 1
    if not pq:  # 如果 pq 沒有資料
        ans -= t - food[idx][0]  # ans 減去 (t - 下一個時物過期的時間)
        t = food[idx][0]  # t 重設為下一個時物過期的時間
    else:  # 如果 pq 有資料
        ans += -hq.heappop(pq)  # 移除 pq 最上方一項，變為正值再加到 ans
        t -= 1  # 時間減 1
print(ans)
```

### C++ 程式碼

執行時間共約為 72 ms，使用記憶體最多約為 4556 kB，通過測試。food 要宣告在 main 外面，如果放在 main 內的第12行，第5筆測資會超時。
```cpp=
#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;

pair<int, int> food[100005];  // 食物的 (保存期限, 熱量)

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 食物數量 n
    //pair<int, int> food[n];  // 食物的 (保存期限, 熱量)
    for(int i=0; i<n; i++) cin >> food[i].second >> food[i].first;  // 讀取 n 行資料
    sort(food, food+n, greater<pair<int, int>>());  // 由大到小排序
    int k; cin >> k;  // 結束時間 k
    int ans = 0, idx = 0, t = k;  // 答案 ans，由 food 讀取資料用的索引值 idx，時刻 t
    priority_queue<int> pq;  // 儲存目前未過期的食物熱量，由大到小排序

    while(t > 0) {  // t > 0 繼續執行 
        while(idx < n && food[idx].first >= t) {  // 如果 idx 還沒有出界而且 food[idx] 還沒有過期
            pq.push(food[idx].second);  // 將 food[idx].second 加入 pq
            idx++;  // idx 加 1
        }
        if(pq.empty()) {  // 如果 pq 沒有資料
            ans -= t - food[idx].first;  // ans 減去 (t - 下一個時物過期的時間)
            t = food[idx].first;  // t 重設為下一個時物過期的時間
        } else {  // 如果 pq 有資料
            ans += pq.top(); pq.pop();  // ans 加上 pq 最上方一項，再移除此項
            t--;  // 時間減 1
        }
    }
    cout << ans << "\n";
    return 0;
}
```


------

###### tags:`演算法`、`APCS`、`Python`、`C++`