# 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++`