一、什么是貪心算法？

貪心算法是一種在每一步選擇中都采取當前看起來最優（最“貪心”）的策略，從而希望得到全局最優解的算法設計思想。

• 核心思想：每一步都做出局部最優選擇，不回退。
• 適用場景：問題具有最優子結構且滿足貪心選擇性質 —— 即局部最優可以導出全局最優。

---

二、貪心算法的典型流程

1. 排序/預處理：對待選元素進行必要的排序或組織。
2. 局部選擇：按照某種規則（如最大收益、最小代價等）依次選取元素。
3. 可行性檢驗：檢查當前選擇是否滿足約束。
4. 解的構造：在每次選擇的基礎上逐步構建最終解。

---

三、經典例題回顧

1. 活動選擇問題

• 題目：有 $n$ 個活動，每個活動有開始時間 $s_i$ 和結束時間 $f_i$，要求選出最多互不沖突的活動集合。
• 貪心策略：按活動結束時間從小到大排序，每次選取結束最早且與當前已選活動不沖突的活動。

2. 分數背包問題（Fractional Knapsack）

• 題目：有 $n$ 件物品，每件物品重量 $w_i$，價值 $v_i$，背包容量 $W$。物品可分割裝入。
• 貪心策略：按單位重量價值 $\frac{v_i}{w_i}$ 從大到小裝入；裝不下時裝入盡可能多的部分。

3. 最小生成樹（Kruskal 算法）

• 題目：給定帶權無向圖，求一棵權值之和最小的生成樹。
• 貪心策略：對所有邊按權值從小到大排序，依次加入不會形成環的最小邊。

---

四、實戰題目 —— 給 $n$ 個國家加稅

4.1 題目描述

• 有 $n$ 個國家，初始關稅稅率均為 100%。
• 對第 $i$ 個國家，加稅一次可將其稅率提升 $p_i\%$（即稅率從上一次的值再加上 $p_i$ 百分點）。
• 允許一共進行 $k$ 次加稅操作，每次只能選擇一個國家進行一次加稅。
• 求經過 $k$ 次加稅后，所有國家稅率的累乘（乘積）的最大值。

示例

輸入：n = 3, p = [2, 5, 3], k = 4  
輸出：最大乘積（按百分比計算）

4.2 貪心思路分析

收益定義

• 對第 $i$ 個國家當前稅率 $t_i$（最開始 $t_i=100\%$）再加一次 $p_i\%$，其新的稅率為 $t_i+p_i$。
• 在乘積中，相當于將當前乘積乘以 $\frac{t_i+p_i}{t_i}$，因此這次操作對總乘積的放大倍數為：

$r_i=\frac{t_i+p_i}{t_i}=1+\frac{p_i}{t_i}$

• 要使乘積最大，每次都應選擇能帶來最大放大倍數 $r_i$ 的國家。

優先隊列實現

• 使用一個最大堆（priority_queue）存儲每個國家當前可獲得的放大倍數 $r_i$。
• 每次取出堆頂（$r_i$ 最大的國家），實施一次加稅：
  1. 更新該國家稅率：$t_i\leftarrow t_i+p_i$。
  2. 計算新的放大倍數：$r_i\leftarrow 1+\frac{p_i}{t_i}$。
  3. 將更新后的 $r_i$ 重新壓入堆中。
• 重復上述過程 $k$ 次，結束后遍歷所有國家稅率，計算乘積。

---

4.3 代碼示例（C++）

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;vector<double> p(n), t(n, 100.0);for (int i = 0; i < n; i++) {cin >> p[i];}// 優先隊列：pair<放大倍數, 國家索引>auto cmp = [](const pair<double,int>& a, const pair<double,int>& b) {return a.first < b.first;};priority_queue<pair<double,int>, vector<pair<double,int>>, decltype(cmp)> pq(cmp);// 初始化for (int i = 0; i < n; i++) {double r = 1.0 + p[i] / t[i];pq.push({r, i});}// 執行 k 次加稅while (k--) {auto [r, i] = pq.top(); pq.pop();t[i] += p[i];r = 1.0 + p[i] / t[i];pq.push({r, i});}// 計算累乘結果double ans = 1.0;for (double tax : t) {ans *= tax / 100.0;}cout << fixed << setprecision(6) << ans << "\n";return 0;
}

---

4.4 復雜度分析

• 每次操作：彈出堆頂 + 插入堆頂，各 $O(\log n)$。
• 總共 $k$ 次操作，時間復雜度為：$O(k\log n)$。
• 空間復雜度：需要存儲 $n$ 個國家的信息，為 $O(n)$。

---

五、更多貪心練習題推薦

1. 區間染色問題：給定區間集合，最少使用多少種顏色使重疊區間不同色？
2. 跳躍游戲 II：每格有最大跳躍長度，求最少跳躍次數到達末尾。
3. 分配餅干：孩子有滿足度，餅干有大小，如何讓最多孩子滿足？
4. 連通區間合并：給一堆區間，合并所有重疊區間，輸出不重疊區間集合。

---

六、小結

• 貪心算法以“當前最優選擇”逐步構建解，適合于“最優子結構”且滿足“貪心選擇性質”的問題。
• 真正的難點在于如何證明局部最優能導出全局最優，以及如何設計合適的貪心策略。
• 通過上述“加稅”題，以及經典例題的練習，可以加深對貪心算法的理解與應用。