--- ###### tags: `2021 師大附中資訊科暑期培訓` --- # 貪心法 2021 師大附中資訊科暑期培訓 joylintp --- ## 每次選擇對當前狀態最有利的決策 --- ## 換硬幣 有 50、10、5、1 四種面額的硬幣， 求至少要多少硬幣才能湊出總額 $k$ 元 ---- * 先盡量用 50 元湊 * 剩下的部分盡量用 10 元湊 * 剩下的部分盡量用 5 元湊 * 剩下的部分用 1 元湊 ---- $ans= \lfloor \frac{k}{50} \rfloor + \lfloor \frac{k\ mod\ 50}{10} \rfloor + \lfloor \frac{k\ mod\ 10}{5} \rfloor + k\ mod\ 5$ --- ## Add All ### ZJ d221 有 $N$ 個數字， 每次可以選擇兩個數字將其合併， 並將兩數字的總和放回序列， 合併所需的成本為兩個數字的總和， 求將所有數字合併成一個的最少總成本為何 ---- <u>1 2</u> 3 // cost = 3 → <u>3 3</u> // cost = 6 → 6 總成本為 9 ---- * 每次選擇最小的兩個數字合併 * 搭配 `priority_queue` 維護最小的兩個數 ---- ```cpp= priority_queue<int, vector<int>, greater<int>> pq; for (int i : arr) pq.push(i); int ans = 0; while (pq.size() > 1) { int t = pq.top(); pq.pop(), t += pq.top(), pq.pop(); pq.push(t), ans += t; } ``` 時間複雜度 $O(N\log{N})$ --- ## 乘船問題 有 $N$ 個人，第 $i$ 個人體重為 $W_i$ 每艘船的限重皆為 $K$，且最多只能乘載兩人 問至少需要幾艘船才能乘載所有人 ---- $N = 5,\ K = 6$ $W = [1, 4, 3, 2, 6]$ → $[1, 3],\ [2, 4],\ [6]$ ---- 考慮尚未上船的體重最輕的人 $i$： * 若剩餘所有人的體重皆超過 $K - W_i$， 則剩下所有人皆一人一艘船 * 否則 $i$ 與體重不超過 $K - W_i$ 的最重的人 坐同一艘船 ---- ```cpp= multiset<int> ms; for (int i : W) ms.insert(i); int ans = 0; while (!ms.empty()) { int Wi = *ms.begin(); ms.erase(ms.begin()); ans++; auto p = ms.upper_bound(K - Wi); if (p != ms.begin()) ms.erase(prev(p)); else { ans += ms.size(); break; } } ``` 時間複雜度 $O(N\log{N})$ --- ## 更多 Greedy ### ZJ a465 (UVa 12405): Scarecrow ### Sprout OJ 91 (UVa 993): 調校高棕櫚！ ### Sprout OJ 89 (NPSC 2005): 誰先晚餐 ### Sprout OJ 78 (UVa 311): 包裝禮物