# 贪心算法专题教程

## 一、 从生活实例理解贪心

### 1.1 找零钱问题
假设你是一家超市的收银员，需要给顾客找零 $36$ 元。你手中有面值为 $20$ 元、$10$ 元、$5$ 元、$1$ 元的纸币。怎样用最少的纸币数量找零？

你可能会这样做：
1. 先拿一张 $20$ 元（剩下 $16$ 元）
2. 再拿一张 $10$ 元（剩下 $6$ 元）
3. 再拿一张 $5$ 元（剩下 $1$ 元）
4. 最后拿一张 $1$ 元

总共用了 $4$ 张纸币。这个想法的核心是：**每次都用当前面值最大的纸币**。用 $20$ 元比用两张 $10$ 元更省纸币，这种“每次选择当前最好的”策略，就是**贪心**。

### 1.2 贪心不一定总是对的
如果把纸币面值换成 $1$ 元、$3$ 元、$4$ 元，要找 $6$ 元：
* **贪心策略**：先拿 $4$ 元（剩 $2$ 元） $\to$ 再拿 $1$ 元 $\to$ 再拿 $1$ 元 $\to$ 共需 $3$ 张。
* **最优解**：$3$ 元 + $3$ 元 $\to$ 共需 $2$ 张。

**结论**：贪心算法不是万能的！它只适用于某些满足特定性质的问题。

### 1.3 找假币问题（分治与贪心的结合）
给你一个装有 $16$ 个硬币的袋子，其中有一个是伪造的。已知伪造的硬币比真硬币稍轻。你的任务是找出这个伪造的硬币。提供一台可用来比较两组硬币重量的仪器，通过它可以知道两组硬币的重量是否相同。

* **方法一（逐个比较）**：先比较硬币1与硬币2。若硬币1轻，则1是伪币；若硬币2轻，则2是伪币；若相等，则说明都不是伪币，继续比较硬币3和硬币4……按此方式，最多通过 $8$ 次比较即可找出伪币。
* **方法二（二分法）**：把 $16$ 个硬币分成两组，每组 $8$ 个。称一次即可确定伪币在哪个组中。再将含有伪币的那组分成两组（每组 $4$ 个）……依此类推，只需 $4$ 次称量就能找出伪币。
* **方法三（三分法）**：把 $16$ 个硬币分成三组：A组 $5$ 个、B组 $5$ 个、C组 $6$ 个。称量 A 和 B：
  * 若平衡，伪币在 C 组（$6$ 个）。再把 C 组分成 2、2、2 三组，称一次确定在哪组，最后再称 $1$ 次即可找出。最多只需 $3$ 次。
  * 若不平衡，伪币在较轻的一组（$5$ 个）。再把该组分成 2、2、1 三组，类似操作，最多也只需 $3$ 次。

这个例子告诉我们：将一个大问题分解成若干个规模较小的相同子问题并逐步解决，是一种重要的算法思想。在每一步都做出当前看起来最优的选择，则是贪心算法的基石。

---

## 二、 贪心算法的基本概念

贪心法在解决最优化问题时，从问题的某一个初始解出发，采用逐步构造最优解的方法向给定的目标前进。在每个局部阶段，都做出一个当前看来最优的决策（局部最优解），并期望通过每次所做的局部最优选择产生出一个全局最优解。

做出贪心决策的依据称为**贪心准则（策略）**。决策一旦做出，就不可再更改。贪心与递推不同，它不是依据某一固定的递推式推进，而是做一个当时看似最佳的贪心选择，不断地将问题实例归纳为更小的相似子问题。因此，**归纳、分析和选择正确合适的贪心准则是关键**。

贪心算法在每一层递归或迭代上都有以下决策步骤：
1. **建立数学模型**：明确问题的输入、输出和约束条件。
2. **分解子问题**：将原问题分解成若干个子问题。
3. **贪心选择**：在每个子问题中做出局部最优选择，然后更新状态。

### 2.1 贪心算法的两个核心性质
一个问题能用贪心算法求解，通常需要满足以下两个性质：

1. **贪心选择性质**：问题的整体最优解可以通过一系列局部最优的贪心选择达到。这是贪心法可行的第一个基本要素，也是它与动态规划的主要区别。
   * **区别**：在动态规划中，每步决策往往依赖于相关子问题的解，因此必须先解出子问题。而贪心算法是先做出局部最优选择，再去解决选择后产生的相应子问题。贪心算法可以依赖以往的选择，但决不依赖将来的选择或子问题的解。
2. **最优子结构性质**：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

### 2.2 贪心算法与动态规划算法的比较
虽然二者都要求具有最优子结构性质，但它们不能混用。例如，0/1 背包问题和部分背包问题都具有最优子结构，但前者不能用贪心（因为存在空间浪费），而必须用动态规划；后者则能用贪心求得最优解。

---

## 三、 删数问题

> **问题描述**
> 键盘输入一个高精度的正整数 $n$（$\le 240$ 位），去掉其中任意 $s$ 个数字后，剩下的数字按原左右次序组成一个新的正整数。
> 编程对给定的 $n$ 和 $s$，寻找一种方案，使得剩下的数字组成的新数最小。
> 
> * **输入**：$n$ 和 $s$。
> * **输出**：最后剩下的最小数。
> * **输入样例**：
>   ```text
>   178543
>   4
>   ```
> * **输出样例**：
>   ```text
>   13
>   ```

### 3.1 问题分析
由于 $n$ 的有效位数高达 $240$ 位，我们需要采用字符串存贮。

如何确定删除哪 $s$ 位？直接删除最大的 $s$ 个数字显然是错误的（例如 $n = 129$, $s = 1$，删最大数 $9$ 剩 $12$；但若删 $2$ 剩 $19$，删 $1$ 剩 $29$。最优解是删除首位 $1$ 得到 $29$ 还是删 $9$ 得到 $12$？此例中删 $9$ 较小，但若是 $n = 912$, $s = 1$，删最大数 $9$ 剩 $12$，比删 $2$ 剩 $91$ 更好）。

为了让剩下的数最小，我们应尽量让高位数字更小。
**贪心策略**：每一步总是选择一个使剩下的数最小的数字删去。即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则**删除第一个递减区间的首字符**（即若 $n[i] > n[i+1]$，则删除 $n[i]$）。

#### 实例演示：$n = 178543, s = 4$
```text
n = 1 7 8 5 4 3
      ↓
第一步：搜索发现 7 < 8 递增，而 8 > 5 下降。删除首个下降位置的前驱 8 → 1 7 5 4 3
第二步：1 7 5 4 3，搜索发现 7 > 5 下降。删除 7 → 1 5 4 3
第三步：1 5 4 3，搜索发现 5 > 4 下降。删除 5 → 1 4 3
第四步：1 4 3，搜索发现 4 > 3 下降。删除 4 → 1 3
```
最终结果为 `13`。

> **注意事项**：
> 1. 每删完一个数字后，前面的数字可能会和后面的数字形成新的递减关系，因此每次删除后要回到串首重新扫描（或使用单调栈优化）。
> 2. 删除后可能会产生前导零，例如 `105` 删去 `1` 后变成 `05`，需要特殊处理，去除无用的前导零（除非整个数字就是 `0`）。

### 3.2 算法框架 (Pascal 风格伪代码)
```pascal
输入 n，s；

while s > 0 do
begin
    i := 1；                    {从串首开始找}
    while (i < length(n)) and (n[i] <= n[i+1]) do
        i := i + 1；
    delete(n, i, 1)；           {删除字符串 n 的第 i 个字符}
    s := s - 1；
end；

while (length(n) > 1) and (n[1] = '0') do
    delete(n, 1, 1)；           {删去串首可能产生的前导零}

输出 n；
```

### 3.3 C++ 代码实现
```cpp
#include <iostream>
#include <string>
using namespace std;

int main() {
    string n;
    int s;
    if (!(cin >> n >> s)) return 0;
    
    while (s > 0) {
        int i = 0;
        // 从串首开始寻找第一个下降的位置
        // 注意：i < (int)n.length() - 1 确保不越界
        while (i < (int)n.length() - 1 && n[i] <= n[i + 1]) {
            i++;
        }
        // 删除第 i 个字符
        n.erase(i, 1);
        s--;
    }
    
    // 去掉前导零
    while (n.length() > 1 && n[0] == '0') {
        n.erase(0, 1);
    }
    
    cout << n << endl;
    
    return 0;
}
```

---

## 四、 取数游戏

> **问题描述**
> 给出 $2 \times n$（$n \le 100$）个自然数（数小于等于 $30000$）。游戏双方分别为 A 方（计算机）和 B 方（玩家）。
> 规则：只允许从数列两端取数。A 先取，然后双方依次轮流。取完时，取得的数字总和最大者获胜；双方和相等则算 A 胜。
> 问：A 方是否存在必胜策略？
> 
> * **输入**：$n$ 以及 $2 \times n$ 个自然数。
> * **输出**：共 $3 \times n + 2$ 行，展示游戏过程（每 3 行为 A 的选择、B 的选择提示及 B 的实际选择），最后输出双方的总得分。

### 4.1 问题分析
设 $n = 4$，数列为：`7 9 3 6 4 2 5 3`。

如果设计一种简单的局部贪心策略——“A 每次都取两端中较大的数”，B 也同样聪明：
* A 取左端 `7`（剩余 `9 3 6 4 2 5 3`）。
* B 取两端中较大的 `9`（剩余 `3 6 4 2 5 3`）。
* A 接着只能在两端取较大值……
以此推导，A 最终可能落败。

然而，我们发现了一个有趣的规律：
初始时有 $2n$ 个数，奇数位置和偶数位置上的数各有 $n$ 个。
* 如果 A 第一次取走了**奇数位置**的数（即第 $1$ 个数），那么剩下数列的两端就都处于**偶数位置**。
* B 无论取左端还是右端，取走的必定是一个**偶数位置**的数。
* B 取完后，剩下数列的两端又都变回了**奇数位置**。
* 依此类推，**A 总能控制并取走所有奇数位置的数，或者所有偶数位置的数。**

**全局贪心策略**：
A 提前计算所有奇数位置的数之和与所有偶数位置的数之和，并选择和较大的那组。这样 A 便有必胜策略。

### 4.2 C++ 代码实现
```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(2 * n + 1);  // 下标从 1 开始
    
    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i];
    }
    
    // 计算奇数位置和偶数位置的和
    int sumOdd = 0, sumEven = 0;
    for (int i = 1; i <= n; i++) {
        sumOdd += a[2 * i - 1];
        sumEven += a[2 * i];
    }
    
    int j;  // j = 1 表示取奇数位置，j = 0 表示取偶数位置
    int SA, SB;
    if (sumOdd >= sumEven) {
        j = 1;
        SA = sumOdd;
        SB = sumEven;
    } else {
        j = 0;
        SA = sumEven;
        SB = sumOdd;
    }
    
    int lp = 1, rp = 2 * n;
    
    for (int i = 1; i <= n; i++) {
        // A 方根据策略取数
        if ((j == 1 && lp % 2 == 1) || (j == 0 && lp % 2 == 0)) {
            cout << "A: " << a[lp] << endl;
            lp++;
        } else {
            cout << "A: " << a[rp] << endl;
            rp--;
        }
        
        // B 方取数
        char ch;
        cout << " B=L/R ? ";
        do {
            cin >> ch;
            if (ch == 'L') {
                cout << "B: " << a[lp] << endl;
                lp++;
            } else if (ch == 'R') {
                cout << "B: " << a[rp] << endl;
                rp--;
            }
        } while (ch != 'L' && ch != 'R');
    }
    
    cout << "SA = " << SA << endl << "SB = " << SB << endl;
    
    return 0;
}
```

---

## 五、 活动选择问题

> **问题描述**
> 假设有一个需要使用某一资源的 $n$ 个活动组成的集合 $S = \{1, 2, \dots, n\}$。该资源一次只能被一个活动占用。
> 每一个活动有一个开始时间 $b\_i$ 和结束时间 $e\_i$（$b\_i \le e\_i$）。若 $b\_i \ge e\_j$ 或 $b\_j \ge e\_i$，则活动 $i$ 和活动 $j$ 兼容。
> 你的任务是：选择由互相兼容的活动组成的最大集合。
> 
> * **输入格式**：
>   ```text
>   n
>   b1 e1
>   ...
>   bn en
>   ```
> * **输出格式**：
>   最大集合中选中的活动序号，以及最大兼容活动数。
> * **样例输入**：
>   ```text
>   11
>   3 5
>   1 4
>   12 14
>   8 12
>   0 6
>   8 11
>   6 10
>   5 7
>   3 8
>   5 9
>   2 13
>   ```
> * **样例输出**：
>   ```text
>   14
>   2 3 6 8
>   ```
>   *(注：样例输出的第一行 14 为最后选中活动的最大结束时间/总占用时刻，第二行为选中的原始活动序号。)*

### 5.1 问题分析
**贪心策略**：
为了能在有限的时间内安排尽可能多的活动，我们每次都应该选择**结束时间最早**的活动，从而为后续活动留出尽可能多的时间。

按结束时间递增对活动进行排序：
$$e\_1' \le e\_2' \le \dots \le e\_n'$$

#### 样例数据排序表
| 活动序号 $i$ | 开始时间 $b\_i$ | 结束时间 $e\_i$ | 排序后的序号 $j$ |
| :---: | :---: | :---: | :---: |
| 1 | 3 | 5 | 2 |
| 2 | 1 | 4 | 1 |
| 3 | 12 | 14 | 11 |
| 4 | 8 | 12 | 9 |
| 5 | 0 | 6 | 3 |
| 6 | 8 | 11 | 8 |
| 7 | 6 | 10 | 7 |
| 8 | 5 | 7 | 4 |
| 9 | 3 | 8 | 5 |
| 10 | 5 | 9 | 6 |
| 11 | 2 | 13 | 10 |

#### 贪心选择过程模拟
```text
时间轴：0  1  2  3  4  5  6  7  8  9  10 11 12 13 14

活动 2 (1-4)： 选，当前结束时间 = 4
活动 1 (3-5)： 开始 3 < 4，冲突，放弃
活动 5 (0-6)： 开始 0 < 4，冲突，放弃
活动 8 (5-7)： 开始 5 ≥ 4，兼容，选，当前结束时间 = 7
活动 9 (3-8)： 开始 3 < 7，冲突，放弃
活动 10(5-9)： 开始 5 < 7，冲突，放弃
活动 7 (6-10)：开始 6 < 7，冲突，放弃
活动 6 (8-11)：开始 8 ≥ 7，兼容，选，当前结束时间 = 11
活动 4 (8-12)：开始 8 < 11，冲突，放弃
活动 11(2-13)：开始 2 < 11，冲突，放弃
活动 3 (12-14)：开始 12 ≥ 11，兼容，选，当前结束时间 = 14
```
最终选中的活动为：`{2, 8, 6, 3}`。

### 5.2 贪心选择性质的证明（交换论证法）
* **证明**：
  设贪心算法得到的解为 $G = \{g\_1, g\_2, \dots, g\_k\}$，最优解为 $O = \{o\_1, o\_2, \dots, o\_m\}$，二者均按结束时间递增排列。我们要证明 $k = m$。
  
  因为 $g\_1$ 是所有活动中结束时间最早的，所以有 $e(g\_1) \le e(o\_1)$。
  * 若 $g\_1 = o\_1$，则问题归约为剔除该活动后的子问题。
  * 若 $g\_1 \neq o\_1$，构造一个新解 $O' = \{g\_1, o\_2, \dots, o\_m\}$。由于 $e(g\_1) \le e(o\_1)$，且 $o\_1$ 与 $o\_2$ 兼容（即 $b(o\_2) \ge e(o\_1)$），所以必然有 $b(o\_2) \ge e(g\_1)$，即 $g\_1$ 与 $o\_2, \dots, o\_m$ 均兼容。因此 $O'$ 是一个合法的可行解，且 $|O'| = |O| = m$。
  
  这说明用贪心选择 $g\_1$ 替换最优解的第一个元素，得到的解仍然是最优解。通过逐步替换，可将 $O$ 转换为 $G$ 且大小不变，即证明了贪心解就是最优解。

### 5.3 C++ 代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int id, start, finish;
};

bool cmp(const Activity& a, const Activity& b) {
    return a.finish < b.finish;  // 按结束时间升序排序
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<Activity> acts(n);
    
    for (int i = 0; i < n; i++) {
        acts[i].id = i + 1;
        cin >> acts[i].start >> acts[i].finish;
    }
    
    sort(acts.begin(), acts.end(), cmp);
    
    vector<int> selected;
    int lastFinish = -1;
    int totalTime = 0;
    
    for (int i = 0; i < n; i++) {
        if (acts[i].start >= lastFinish) {
            selected.push_back(acts[i].id);
            lastFinish = acts[i].finish;
            totalTime = acts[i].finish;
        }
    }
    
    cout << totalTime << endl;
    for (int i = 0; i < (int)selected.size(); i++) {
        cout << selected[i] << (i == (int)selected.size() - 1 ? "" : " ");
    }
    cout << endl;
    
    return 0;
}
```

---

## 六、 部分背包问题

> **问题描述**
> 有一个容量为 $W$ 的背包和 $n$ 件物品。第 $i$ 件物品重量为 $w\_i$，价值为 $v\_i$。
> 物品可以分割（例如金粉，可以只拿走一部分）。如何装入才能使总价值最大？

### 6.1 问题分析
部分背包问题与 0/1 背包问题的核心区别在于：**物品可分割**。
因此，我们可以采用**性价比（单位重量价值 $v\_i/w\_i$）降序**的贪心策略。每次都尽量多地装入当前性价比最高的物品，直到背包装满。

### 6.2 C++ 代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Item {
    double weight, value;
};

bool cmp(const Item& a, const Item& b) {
    return (a.value / a.weight) > (b.value / b.weight);  // 性价比降序
}

int main() {
    int n;
    double W;
    if (!(cin >> n >> W)) return 0;
    vector<Item> items(n);
    
    for (int i = 0; i < n; i++) {
        cin >> items[i].weight >> items[i].value;
    }
    
    sort(items.begin(), items.end(), cmp);
    
    double ans = 0;
    double remaining = W;
    
    for (int i = 0; i < n && remaining > 0; i++) {
        if (items[i].weight <= remaining) {
            // 可以完整装下
            ans += items[i].value;
            remaining -= items[i].weight;
        } else {
            // 只能装下一部分
            ans += (items[i].value / items[i].weight) * remaining;
            break;
        }
    }
    
    cout << fixed << setprecision(2) << ans << endl;
    
    return 0;
}
```

### 6.3 为什么 0/1 背包不能用贪心？
0/1 背包问题中，物品不可分割。如果盲目使用性价比贪心，会因为“空间无法完美填满”而导致浪费，最终使得总价值降低。
* **反例**：背包容量 $W = 30$。
  * 物品 A：重 $20$，价值 $40$（性价比 = $2.0$）
  * 物品 B：重 $15$，价值 $25$（性价比 = $1.67$）
  * 物品 C：重 $15$，价值 $25$（性价比 = $1.67$）
* **贪心策略**：先装 A，余下容量 $10$，无法再装 B 或 C。总价值为 $40$。
* **最优解**：装 B 和 C，总重量 $30$。总价值为 $50$。

---

## 七、 哈夫曼编码（合并果子）

> **问题描述**
> 有 $n$ 堆果子，每次可以合并任意两堆。合并所需的体力消耗等于两堆果子的重量之和。
> 求将所有果子合并为一堆所需的最小总体力消耗。
> 
> * **样例输入**：
>   ```text
>   3
>   1 2 9
>   ```
> * **样例输出**：
>   ```text
>   15
>   ```
>   *(解释：先合并 1 和 2 消耗 3，得到重量为 3 的新堆；再合并 3 和 9 消耗 12。总消耗 = 3 + 12 = 15)*

### 7.1 问题分析
这是经典的哈夫曼树构造问题。
**贪心策略**：每次都选择当前**重量最小的两堆**进行合并。

#### 交换论证法证明
设最优解中第一次合并的不是最小的两堆 $x$ 和 $y$（设 $x \le y$），而是 $x$ 和某个更大的堆 $z$（$z \ge y$）。
如果在决策树中交换 $y$ 和 $z$ 的位置，合并 $x$ 与 $y$ 的代价为 $x + y$，小于或等于合并 $x$ 与 $z$ 的代价 $x + z$。并且由于 $y$ 处于更深的叶子节点，总代价不会增加，甚至可能变小。因此，每次合并最小的两堆一定是最优的。

### 7.2 C++ 代码实现
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    // 小顶堆：自动维护并输出最小值
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pq.push(x);
    }
    
    long long ans = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        long long sum = a + b;
        ans += sum;
        pq.push(sum);
    }
    
    cout << ans << endl;
    
    return 0;
}
```

* **时间复杂度**：使用优先队列，每次操作时间复杂度为 $O(\log n)$，共合并 $n-1$ 次，总体时间复杂度为 $O(n \log n)$。

---

## 八、 国王游戏

> **问题描述**
> 国王和 $n$ 位大臣的左、右手各写有一个数字。他们排成一排，国王排在最前面。
> 每一位大臣获得的奖励为：**他前面所有人左手数字的乘积** 除以 **他自己右手上的数字**。
> $$\text{奖励} = \frac{\prod\_{j=0}^{i-1} a\_j}{b\_i}$$
> 其中国王的左手数字为 $a\_0$，右手为 $b\_0$（国王不参与奖励计算）。
> 问如何排列大臣，使得获得奖励最多的大臣拿到的奖励最少？

### 8.1 问题分析（邻项交换法）
设排在相邻位置的两位大臣为 $i$ 和 $j$。设他们前面所有人的左手乘积为 $P$。

#### 方案 1：$i$ 在前，$j$ 在后
* 大臣 $i$ 的奖励：$R\_i = \frac{P}{b\_i}$
* 大臣 $j$ 的奖励：$R\_j = \frac{P \times a\_i}{b\_j}$
* 两人中的最大奖励：$\max\left(\frac{P}{b\_i}, \frac{P \times a\_i}{b\_j}\right)$

#### 方案 2：$j$ 在前，$i$ 在后
* 大臣 $j$ 的奖励：$R\_j' = \frac{P}{b\_j}$
* 大臣 $i$ 的奖励：$R\_i' = \frac{P \times a\_j}{b\_i}$
* 两人中的最大奖励：$\max\left(\frac{P}{b\_j}, \frac{P \times a\_j}{b\_i}\right)$

若想让方案 1 优于方案 2，只需满足：
$$\max\left(\frac{P}{b\_i}, \frac{P \times a\_i}{b\_j}\right) \le \max\left(\frac{P}{b\_j}, \frac{P \times a\_j}{b\_i}\right)$$

两边同除 $P$ 并乘 $b\_i b\_j$，得：
$$\max(b\_j, a\_i b\_i) \le \max(b\_i, a\_j b\_j)$$

因为 $a\_i, b\_i \ge 1$，显然有 $a\_i b\_i \ge b\_i$ 且 $a\_j b\_j \ge b\_j$。
要使上式成立，只需：
$$a\_i b\_i \le a\_j b\_j$$

**贪心策略**：按 **左、右手数字的乘积 $a\_i \times b\_i$ 从小到大** 进行升序排序。

### 8.2 C++ 高精度代码实现
由于乘积非常大，会超出 64 位整型的范围，需要配合高精度计算。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Minister {
    int left, right;
};

bool cmp(const Minister& a, const Minister& b) {
    return (long long)a.left * a.right < (long long)b.left * b.right;
}

struct BigInt {
    vector<int> digits;  // 低位在前
    
    BigInt() {}
    BigInt(int x) {
        if (x == 0) { digits.push_back(0); return; }
        while (x > 0) {
            digits.push_back(x % 10);
            x /= 10;
        }
    }
    
    BigInt multiply(int x) const {
        BigInt res;
        res.digits.clear();
        int carry = 0;
        for (size_t i = 0; i < digits.size() || carry; i++) {
            long long cur = carry;
            if (i < digits.size()) {
                cur += (long long)digits[i] * x;
            }
            res.digits.push_back(cur % 10);
            carry = cur / 10;
        }
        while (res.digits.size() > 1 && res.digits.back() == 0) {
            res.digits.pop_back();
        }
        return res;
    }
    
    BigInt divide(int x) const {
        BigInt res;
        res.digits.clear();
        long long remainder = 0;
        for (int i = (int)digits.size() - 1; i >= 0; i--) {
            remainder = remainder * 10 + digits[i];
            res.digits.push_back(remainder / x);
            remainder %= x;
        }
        reverse(res.digits.begin(), res.digits.end());
        while (res.digits.size() > 1 && res.digits.back() == 0) {
            res.digits.pop_back();
        }
        return res;
    }
    
    bool lessThan(const BigInt& other) const {
        if (digits.size() != other.digits.size()) {
            return digits.size() < other.digits.size();
        }
        for (int i = (int)digits.size() - 1; i >= 0; i--) {
            if (digits[i] != other.digits[i]) {
                return digits[i] < other.digits[i];
            }
        }
        return false;
    }
    
    void print() const {
        for (int i = (int)digits.size() - 1; i >= 0; i--) {
            cout << digits[i];
        }
    }
};

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    int kingLeft, kingRight;
    cin >> kingLeft >> kingRight;
    
    vector<Minister> ministers(n);
    for (int i = 0; i < n; i++) {
        cin >> ministers[i].left >> ministers[i].right;
    }
    
    sort(ministers.begin(), ministers.end(), cmp);
    
    BigInt product(kingLeft);
    BigInt maxReward(0);
    
    for (int i = 0; i < n; i++) {
        BigInt reward = product.divide(ministers[i].right);
        if (maxReward.lessThan(reward)) {
            maxReward = reward;
        }
        product = product.multiply(ministers[i].left);
    }
    
    maxReward.print();
    cout << endl;
    
    return 0;
}
```

---

## 九、 雇佣计划

> **问题描述**
> 经理需要确定每个月雇佣的工人数，已知每月最少需要的工人数。
> * 雇佣新工人费用为 $h$/人，解雇工人费用为 $f$/人。
> * 工人在职期间，即使不干活也需要支付工资 $s$/月/人。
> 求 $n$ 个月控制总费用的最低方案。

### 9.1 问题分析与贪心思想
当月实际工人数 `now` 必须满足当月最小需求 `need[i]`。

1. **若人数不足 (`need[i] > now`)**：必须新雇佣 $need[i] - now$ 人，使人数恰好达到最低限度。
2. **若人数多余 (`need[i] < now`)**：是否立即解雇多余的工人？
   * **考虑**：如果未来几个月内还需要同样多的人手，解雇后再重新雇佣的费用 $f + h$ 可能大于维持多余人手所支付的额外工资。
   * **贪心策略**：向后搜索未来月份。若保留这些人付出的额外工资，小于解雇并重新雇佣的费用，则选择不解雇，维持当前人数。

### 9.2 C++ 代码实现
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    int h, s, f;
    cin >> h >> s >> f;
    
    vector<int> need(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> need[i];
    }
    
    int mincost = 0;
    int now = 0;
    
    for (int i = 1; i <= n; i++) {
        if (need[i] > now) {
            // 人手不足，必须雇佣
            mincost += h * (need[i] - now);
            now = need[i];
        } else if (need[i] < now) {
            // 人手多余，决策是否解雇
            bool keep = false;
            for (int j = i + 1; j <= n; j++) {
                if (need[j] >= now) {
                    keep = true;
                    break;
                }
                if (need[j] >= need[i]) {
                    // 额外工资总额 vs 解雇与重新雇佣成本
                    int extraWage = s * (j - i) * (now - need[j]); 
                    int costFireHire = (f + h) * (now - need[j]);
                    if (costFireHire > extraWage) {
                        keep = true;
                        break;
                    }
                }
            }
            if (!keep) {
                // 解雇多余人手至当月最低限度
                mincost += f * (now - need[i]);
                now = need[i];
            }
        }
        mincost += now * s; // 支付当月工资
    }
    
    cout << mincost << endl;
    return 0;
}
```

---

## 十、 贪心算法在树和图论中的应用

图论中许多经典的高效算法都深度应用了贪心思想。

### 10.1 最小生成树 (MST)
* **Prim 算法**：从任意顶点开始逐步向外扩展树。每一步选择一条**连接树内顶点与树外顶点中权重最小的边**。
* **Kruskal 算法**：将所有边按权重从小到大排序，每次选择**不与已选边构成环的权值最小的边**。

```cpp
// Kruskal 算法核心贪心选择
sort(edges.begin(), edges.end(), cmp);
for (Edge e : edges) {
    int fu = find(e.u), fv = find(e.v);
    if (fu != fv) {
        parent[fu] = fv;
        ans += e.w;
        cnt++;
        if (cnt == n - 1) break;
    }
}
```

### 10.2 单源最短路径 (Dijkstra 算法)
用于求解无负权图的单源最短路径。
* **贪心策略**：每次从未确定最短路径的节点中，选择一个**当前距离源点最近的节点 $u$**，加入已确定集合，并用它更新相邻节点的距离（松弛操作）。

```cpp
// Dijkstra 算法核心贪心选择
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> dist(n+1, INF);
dist[s] = 0;
pq.push({0, s});

while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w] : g[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}
```

---

## 十一、 小结

### 11.1 贪心算法的基本要素
1. **贪心选择性质**：可以通过一系列局部最优决策达到全局最优。
2. **最优子结构性质**：问题的最优解包含其子问题的最优解。

### 11.2 证明方法
由于贪心策略往往伴随着直觉，在设计出算法后，通常需要进行合理性证明：
* **交换论证法**：假设存在一个最优解，证明将其中的非贪心决策替换为贪心决策后，解不会变差。
* **数学归纳法**：适用于阶段性递推明显的问题。
* **反例构造法**：在思考贪心准则时，多尝试构造小规模的极限数据来推翻错误的直觉。

贪心算法专题教程

一、从生活实例理解贪心

1.1 找零钱问题

假设你是一家超市的收银员，需要给顾客找零 $36$ 元。你手中有面值为 $20$ 元、$10$ 元、$5$ 元、$1$ 元的纸币。怎样用最少的纸币数量找零？

你可能会这样做： 1. 先拿一张 $20$ 元（剩下 $16$ 元） 2. 再拿一张 $10$ 元（剩下 $6$ 元） 3. 再拿一张 $5$ 元（剩下 $1$ 元） 4. 最后拿一张 $1$ 元

总共用了 $4$ 张纸币。这个想法的核心是：每次都用当前面值最大的纸币。用 $20$ 元比用两张 $10$ 元更省纸币，这种“每次选择当前最好的”策略，就是贪心。

1.2 贪心不一定总是对的

如果把纸币面值换成 $1$ 元、$3$ 元、$4$ 元，要找 $6$ 元： * 贪心策略：先拿 $4$ 元（剩 $2$ 元） $\to$ 再拿 $1$ 元 $\to$ 再拿 $1$ 元 $\to$ 共需 $3$ 张。 * 最优解：$3$ 元 + $3$ 元 $\to$ 共需 $2$ 张。

结论：贪心算法不是万能的！它只适用于某些满足特定性质的问题。

1.3 找假币问题（分治与贪心的结合）

给你一个装有 $16$ 个硬币的袋子，其中有一个是伪造的。已知伪造的硬币比真硬币稍轻。你的任务是找出这个伪造的硬币。提供一台可用来比较两组硬币重量的仪器，通过它可以知道两组硬币的重量是否相同。

方法一（逐个比较）：先比较硬币1与硬币2。若硬币1轻，则1是伪币；若硬币2轻，则2是伪币；若相等，则说明都不是伪币，继续比较硬币3和硬币4……按此方式，最多通过 $8$ 次比较即可找出伪币。
方法二（二分法）：把 $16$ 个硬币分成两组，每组 $8$ 个。称一次即可确定伪币在哪个组中。再将含有伪币的那组分成两组（每组 $4$ 个）……依此类推，只需 $4$ 次称量就能找出伪币。
方法三（三分法）：把 $16$ 个硬币分成三组：A组 $5$ 个、B组 $5$ 个、C组 $6$ 个。称量 A 和 B：
若平衡，伪币在 C 组（$6$ 个）。再把 C 组分成 2、2、2 三组，称一次确定在哪组，最后再称 $1$ 次即可找出。最多只需 $3$ 次。
若不平衡，伪币在较轻的一组（$5$ 个）。再把该组分成 2、2、1 三组，类似操作，最多也只需 $3$ 次。

二、贪心算法的基本概念

做出贪心决策的依据称为贪心准则（策略）。决策一旦做出，就不可再更改。贪心与递推不同，它不是依据某一固定的递推式推进，而是做一个当时看似最佳的贪心选择，不断地将问题实例归纳为更小的相似子问题。因此，归纳、分析和选择正确合适的贪心准则是关键。

贪心算法在每一层递归或迭代上都有以下决策步骤： 1. 建立数学模型：明确问题的输入、输出和约束条件。 2. 分解子问题：将原问题分解成若干个子问题。 3. 贪心选择：在每个子问题中做出局部最优选择，然后更新状态。

2.1 贪心算法的两个核心性质

一个问题能用贪心算法求解，通常需要满足以下两个性质：

贪心选择性质：问题的整体最优解可以通过一系列局部最优的贪心选择达到。这是贪心法可行的第一个基本要素，也是它与动态规划的主要区别。
区别：在动态规划中，每步决策往往依赖于相关子问题的解，因此必须先解出子问题。而贪心算法是先做出局部最优选择，再去解决选择后产生的相应子问题。贪心算法可以依赖以往的选择，但决不依赖将来的选择或子问题的解。
最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

2.2 贪心算法与动态规划算法的比较

虽然二者都要求具有最优子结构性质，但它们不能混用。例如，0/1 背包问题和部分背包问题都具有最优子结构，但前者不能用贪心（因为存在空间浪费），而必须用动态规划；后者则能用贪心求得最优解。

对比项	贪心算法	动态规划
决策方式	只考虑当前，做出局部最优选择	考虑所有可能，保留并递推多种状态
子问题关系	沿单方向进行，子问题独立或顺次解决	需要求解并组合所有子问题的解
效率	通常更快（$O(n \log n)$ 或 $O(n)$）	较慢（$O(n^2)$ 或更高）
适用范围	满足贪心选择性质的问题	有最优子结构和重叠子问题的问题
是否保证最优	不一定（需严格证明）	一定能得到最优解

三、删数问题

问题描述 键盘输入一个高精度的正整数 $n$（$\le 240$ 位），去掉其中任意 $s$ 个数字后，剩下的数字按原左右次序组成一个新的正整数。编程对给定的 $n$ 和 $s$，寻找一种方案，使得剩下的数字组成的新数最小。

输入：$n$ 和 $s$。

输出：最后剩下的最小数。

输入样例： text 178543 4

输出样例： text 13

3.1 问题分析

由于 $n$ 的有效位数高达 $240$ 位，我们需要采用字符串存贮。

为了让剩下的数最小，我们应尽量让高位数字更小。 贪心策略：每一步总是选择一个使剩下的数最小的数字删去。即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符（即若 $n[i] > n[i+1]$，则删除 $n[i]$）。

实例演示：$n = 178543, s = 4$

n = 1 7 8 5 4 3
      ↓
第一步：搜索发现 7 < 8 递增，而 8 > 5 下降。删除首个下降位置的前驱 8 → 1 7 5 4 3
第二步：1 7 5 4 3，搜索发现 7 > 5 下降。删除 7 → 1 5 4 3
第三步：1 5 4 3，搜索发现 5 > 4 下降。删除 5 → 1 4 3
第四步：1 4 3，搜索发现 4 > 3 下降。删除 4 → 1 3

最终结果为 13。

注意事项： 1. 每删完一个数字后，前面的数字可能会和后面的数字形成新的递减关系，因此每次删除后要回到串首重新扫描（或使用单调栈优化）。 2. 删除后可能会产生前导零，例如 105 删去 1 后变成 05，需要特殊处理，去除无用的前导零（除非整个数字就是 0）。

3.2 算法框架 (Pascal 风格伪代码)

输入 n，s；

while s > 0 do
begin
    i := 1；                    {从串首开始找}
    while (i < length(n)) and (n[i] <= n[i+1]) do
        i := i + 1；
    delete(n, i, 1)；           {删除字符串 n 的第 i 个字符}
    s := s - 1；
end；

while (length(n) > 1) and (n[1] = '0') do
    delete(n, 1, 1)；           {删去串首可能产生的前导零}

输出 n；

3.3 C++ 代码实现

#include <iostream>
#include <string>
using namespace std;

int main() {
    string n;
    int s;
    if (!(cin >> n >> s)) return 0;

    while (s > 0) {
        int i = 0;
        // 从串首开始寻找第一个下降的位置
        // 注意：i < (int)n.length() - 1 确保不越界
        while (i < (int)n.length() - 1 && n[i] <= n[i + 1]) {
            i++;
        }
        // 删除第 i 个字符
        n.erase(i, 1);
        s--;
    }

    // 去掉前导零
    while (n.length() > 1 && n[0] == '0') {
        n.erase(0, 1);
    }

    cout << n << endl;

    return 0;
}

四、取数游戏

问题描述 给出 $2 \times n$（$n \le 100$）个自然数（数小于等于 $30000$）。游戏双方分别为 A 方（计算机）和 B 方（玩家）。规则：只允许从数列两端取数。A 先取，然后双方依次轮流。取完时，取得的数字总和最大者获胜；双方和相等则算 A 胜。问：A 方是否存在必胜策略？

输入：$n$ 以及 $2 \times n$ 个自然数。

输出：共 $3 \times n + 2$ 行，展示游戏过程（每 3 行为 A 的选择、B 的选择提示及 B 的实际选择），最后输出双方的总得分。

4.1 问题分析

设 $n = 4$，数列为：7 9 3 6 4 2 5 3。

如果设计一种简单的局部贪心策略——“A 每次都取两端中较大的数”，B 也同样聪明： * A 取左端 7（剩余 9 3 6 4 2 5 3）。 * B 取两端中较大的 9（剩余 3 6 4 2 5 3）。 * A 接着只能在两端取较大值…… 以此推导，A 最终可能落败。

然而，我们发现了一个有趣的规律：初始时有 $2n$ 个数，奇数位置和偶数位置上的数各有 $n$ 个。 * 如果 A 第一次取走了奇数位置的数（即第 $1$ 个数），那么剩下数列的两端就都处于偶数位置。 * B 无论取左端还是右端，取走的必定是一个偶数位置的数。 * B 取完后，剩下数列的两端又都变回了奇数位置。 * 依此类推，A 总能控制并取走所有奇数位置的数，或者所有偶数位置的数。

全局贪心策略： A 提前计算所有奇数位置的数之和与所有偶数位置的数之和，并选择和较大的那组。这样 A 便有必胜策略。

4.2 C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(2 * n + 1);  // 下标从 1 开始

    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i];
    }

    // 计算奇数位置和偶数位置的和
    int sumOdd = 0, sumEven = 0;
    for (int i = 1; i <= n; i++) {
        sumOdd += a[2 * i - 1];
        sumEven += a[2 * i];
    }

    int j;  // j = 1 表示取奇数位置，j = 0 表示取偶数位置
    int SA, SB;
    if (sumOdd >= sumEven) {
        j = 1;
        SA = sumOdd;
        SB = sumEven;
    } else {
        j = 0;
        SA = sumEven;
        SB = sumOdd;
    }

    int lp = 1, rp = 2 * n;

    for (int i = 1; i <= n; i++) {
        // A 方根据策略取数
        if ((j == 1 && lp % 2 == 1) || (j == 0 && lp % 2 == 0)) {
            cout << "A: " << a[lp] << endl;
            lp++;
        } else {
            cout << "A: " << a[rp] << endl;
            rp--;
        }

        // B 方取数
        char ch;
        cout << " B=L/R ? ";
        do {
            cin >> ch;
            if (ch == 'L') {
                cout << "B: " << a[lp] << endl;
                lp++;
            } else if (ch == 'R') {
                cout << "B: " << a[rp] << endl;
                rp--;
            }
        } while (ch != 'L' && ch != 'R');
    }

    cout << "SA = " << SA << endl << "SB = " << SB << endl;

    return 0;
}

五、活动选择问题

问题描述 假设有一个需要使用某一资源的 $n$ 个活动组成的集合 $S = {1, 2, \dots, n}$。该资源一次只能被一个活动占用。每一个活动有一个开始时间 $b_i$ 和结束时间 $e_i$（$b_i \le e_i$）。若 $b_i \ge e_j$ 或 $b_j \ge e_i$，则活动 $i$ 和活动 $j$ 兼容。你的任务是：选择由互相兼容的活动组成的最大集合。

输入格式： text n b1 e1 ... bn en

输出格式：最大集合中选中的活动序号，以及最大兼容活动数。

样例输入： text 11 3 5 1 4 12 14 8 12 0 6 8 11 6 10 5 7 3 8 5 9 2 13

样例输出： text 14 2 3 6 8 (注：样例输出的第一行 14 为最后选中活动的最大结束时间/总占用时刻，第二行为选中的原始活动序号。)

5.1 问题分析

贪心策略：为了能在有限的时间内安排尽可能多的活动，我们每次都应该选择结束时间最早的活动，从而为后续活动留出尽可能多的时间。

按结束时间递增对活动进行排序： $$e_1' \le e_2' \le \dots \le e_n'$$

样例数据排序表

活动序号 $i$	开始时间 $b_i$	结束时间 $e_i$	排序后的序号 $j$
1	3	5	2
2	1	4	1
3	12	14	11
4	8	12	9
5	0	6	3
6	8	11	8
7	6	10	7
8	5	7	4
9	3	8	5
10	5	9	6
11	2	13	10

贪心选择过程模拟

时间轴：0  1  2  3  4  5  6  7  8  9  10 11 12 13 14

活动 2 (1-4)： 选，当前结束时间 = 4
活动 1 (3-5)： 开始 3 < 4，冲突，放弃
活动 5 (0-6)： 开始 0 < 4，冲突，放弃
活动 8 (5-7)： 开始 5 ≥ 4，兼容，选，当前结束时间 = 7
活动 9 (3-8)： 开始 3 < 7，冲突，放弃
活动 10(5-9)： 开始 5 < 7，冲突，放弃
活动 7 (6-10)：开始 6 < 7，冲突，放弃
活动 6 (8-11)：开始 8 ≥ 7，兼容，选，当前结束时间 = 11
活动 4 (8-12)：开始 8 < 11，冲突，放弃
活动 11(2-13)：开始 2 < 11，冲突，放弃
活动 3 (12-14)：开始 12 ≥ 11，兼容，选，当前结束时间 = 14

最终选中的活动为：{2, 8, 6, 3}。

5.2 贪心选择性质的证明（交换论证法）

证明：设贪心算法得到的解为 $G = {g_1, g_2, \dots, g_k}$，最优解为 $O = {o_1, o_2, \dots, o_m}$，二者均按结束时间递增排列。我们要证明 $k = m$。

因为 $g_1$ 是所有活动中结束时间最早的，所以有 $e(g_1) \le e(o_1)$。 * 若 $g_1 = o_1$，则问题归约为剔除该活动后的子问题。 * 若 $g_1 \neq o_1$，构造一个新解 $O' = {g_1, o_2, \dots, o_m}$。由于 $e(g_1) \le e(o_1)$，且 $o_1$ 与 $o_2$ 兼容（即 $b(o_2) \ge e(o_1)$），所以必然有 $b(o_2) \ge e(g_1)$，即 $g_1$ 与 $o_2, \dots, o_m$ 均兼容。因此 $O'$ 是一个合法的可行解，且 $|O'| = |O| = m$。

这说明用贪心选择 $g_1$ 替换最优解的第一个元素，得到的解仍然是最优解。通过逐步替换，可将 $O$ 转换为 $G$ 且大小不变，即证明了贪心解就是最优解。

5.3 C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int id, start, finish;
};

bool cmp(const Activity& a, const Activity& b) {
    return a.finish < b.finish;  // 按结束时间升序排序
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<Activity> acts(n);

    for (int i = 0; i < n; i++) {
        acts[i].id = i + 1;
        cin >> acts[i].start >> acts[i].finish;
    }

    sort(acts.begin(), acts.end(), cmp);

    vector<int> selected;
    int lastFinish = -1;
    int totalTime = 0;

    for (int i = 0; i < n; i++) {
        if (acts[i].start >= lastFinish) {
            selected.push_back(acts[i].id);
            lastFinish = acts[i].finish;
            totalTime = acts[i].finish;
        }
    }

    cout << totalTime << endl;
    for (int i = 0; i < (int)selected.size(); i++) {
        cout << selected[i] << (i == (int)selected.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

六、部分背包问题

问题描述 有一个容量为 $W$ 的背包和 $n$ 件物品。第 $i$ 件物品重量为 $w_i$，价值为 $v_i$。物品可以分割（例如金粉，可以只拿走一部分）。如何装入才能使总价值最大？

6.1 问题分析

部分背包问题与 0/1 背包问题的核心区别在于：物品可分割。因此，我们可以采用性价比（单位重量价值 $v_i/w_i$）降序的贪心策略。每次都尽量多地装入当前性价比最高的物品，直到背包装满。

6.2 C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Item {
    double weight, value;
};

bool cmp(const Item& a, const Item& b) {
    return (a.value / a.weight) > (b.value / b.weight);  // 性价比降序
}

int main() {
    int n;
    double W;
    if (!(cin >> n >> W)) return 0;
    vector<Item> items(n);

    for (int i = 0; i < n; i++) {
        cin >> items[i].weight >> items[i].value;
    }

    sort(items.begin(), items.end(), cmp);

    double ans = 0;
    double remaining = W;

    for (int i = 0; i < n && remaining > 0; i++) {
        if (items[i].weight <= remaining) {
            // 可以完整装下
            ans += items[i].value;
            remaining -= items[i].weight;
        } else {
            // 只能装下一部分
            ans += (items[i].value / items[i].weight) * remaining;
            break;
        }
    }

    cout << fixed << setprecision(2) << ans << endl;

    return 0;
}

6.3 为什么 0/1 背包不能用贪心？

0/1 背包问题中，物品不可分割。如果盲目使用性价比贪心，会因为“空间无法完美填满”而导致浪费，最终使得总价值降低。 * 反例：背包容量 $W = 30$。 * 物品 A：重 $20$，价值 $40$（性价比 = $2.0$） * 物品 B：重 $15$，价值 $25$（性价比 = $1.67$） * 物品 C：重 $15$，价值 $25$（性价比 = $1.67$） * 贪心策略：先装 A，余下容量 $10$，无法再装 B 或 C。总价值为 $40$。 * 最优解：装 B 和 C，总重量 $30$。总价值为 $50$。

七、哈夫曼编码（合并果子）

问题描述 有 $n$ 堆果子，每次可以合并任意两堆。合并所需的体力消耗等于两堆果子的重量之和。求将所有果子合并为一堆所需的最小总体力消耗。

样例输入： text 3 1 2 9

样例输出： text 15 (解释：先合并 1 和 2 消耗 3，得到重量为 3 的新堆；再合并 3 和 9 消耗 12。总消耗 = 3 + 12 = 15)

7.1 问题分析

这是经典的哈夫曼树构造问题。 贪心策略：每次都选择当前重量最小的两堆进行合并。

交换论证法证明

设最优解中第一次合并的不是最小的两堆 $x$ 和 $y$（设 $x \le y$），而是 $x$ 和某个更大的堆 $z$（$z \ge y$）。如果在决策树中交换 $y$ 和 $z$ 的位置，合并 $x$ 与 $y$ 的代价为 $x + y$，小于或等于合并 $x$ 与 $z$ 的代价 $x + z$。并且由于 $y$ 处于更深的叶子节点，总代价不会增加，甚至可能变小。因此，每次合并最小的两堆一定是最优的。

7.2 C++ 代码实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    // 小顶堆：自动维护并输出最小值
    priority_queue<long long, vector<long long>, greater<long long>> pq;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pq.push(x);
    }

    long long ans = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        long long sum = a + b;
        ans += sum;
        pq.push(sum);
    }

    cout << ans << endl;

    return 0;
}

时间复杂度：使用优先队列，每次操作时间复杂度为 $O(\log n)$，共合并 $n-1$ 次，总体时间复杂度为 $O(n \log n)$。

八、国王游戏

问题描述 国王和 $n$ 位大臣的左、右手各写有一个数字。他们排成一排，国王排在最前面。每一位大臣获得的奖励为：他前面所有人左手数字的乘积 除以 他自己右手上的数字。 $$\text{奖励} = \frac{\prod_{j=0}^{i-1} a_j}{b_i}$$ 其中国王的左手数字为 $a_0$，右手为 $b_0$（国王不参与奖励计算）。问如何排列大臣，使得获得奖励最多的大臣拿到的奖励最少？

8.1 问题分析（邻项交换法）

设排在相邻位置的两位大臣为 $i$ 和 $j$。设他们前面所有人的左手乘积为 $P$。

方案 1：$i$ 在前，$j$ 在后

大臣 $i$ 的奖励：$R_i = \frac{P}{b_i}$
大臣 $j$ 的奖励：$R_j = \frac{P \times a_i}{b_j}$
两人中的最大奖励：$\max\left(\frac{P}{b_i}, \frac{P \times a_i}{b_j}\right)$

方案 2：$j$ 在前，$i$ 在后

大臣 $j$ 的奖励：$R_j' = \frac{P}{b_j}$
大臣 $i$ 的奖励：$R_i' = \frac{P \times a_j}{b_i}$
两人中的最大奖励：$\max\left(\frac{P}{b_j}, \frac{P \times a_j}{b_i}\right)$

若想让方案 1 优于方案 2，只需满足： $$\max\left(\frac{P}{b_i}, \frac{P \times a_i}{b_j}\right) \le \max\left(\frac{P}{b_j}, \frac{P \times a_j}{b_i}\right)$$

两边同除 $P$ 并乘 $b_i b_j$，得： $$\max(b_j, a_i b_i) \le \max(b_i, a_j b_j)$$

因为 $a_i, b_i \ge 1$，显然有 $a_i b_i \ge b_i$ 且 $a_j b_j \ge b_j$。要使上式成立，只需： $$a_i b_i \le a_j b_j$$

贪心策略：按 左、右手数字的乘积 $a_i \times b_i$ 从小到大 进行升序排序。

8.2 C++ 高精度代码实现

由于乘积非常大，会超出 64 位整型的范围，需要配合高精度计算。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Minister {
    int left, right;
};

bool cmp(const Minister& a, const Minister& b) {
    return (long long)a.left * a.right < (long long)b.left * b.right;
}

struct BigInt {
    vector<int> digits;  // 低位在前

    BigInt() {}
    BigInt(int x) {
        if (x == 0) { digits.push_back(0); return; }
        while (x > 0) {
            digits.push_back(x % 10);
            x /= 10;
        }
    }

    BigInt multiply(int x) const {
        BigInt res;
        res.digits.clear();
        int carry = 0;
        for (size_t i = 0; i < digits.size() || carry; i++) {
            long long cur = carry;
            if (i < digits.size()) {
                cur += (long long)digits[i] * x;
            }
            res.digits.push_back(cur % 10);
            carry = cur / 10;
        }
        while (res.digits.size() > 1 && res.digits.back() == 0) {
            res.digits.pop_back();
        }
        return res;
    }

    BigInt divide(int x) const {
        BigInt res;
        res.digits.clear();
        long long remainder = 0;
        for (int i = (int)digits.size() - 1; i >= 0; i--) {
            remainder = remainder * 10 + digits[i];
            res.digits.push_back(remainder / x);
            remainder %= x;
        }
        reverse(res.digits.begin(), res.digits.end());
        while (res.digits.size() > 1 && res.digits.back() == 0) {
            res.digits.pop_back();
        }
        return res;
    }

    bool lessThan(const BigInt& other) const {
        if (digits.size() != other.digits.size()) {
            return digits.size() < other.digits.size();
        }
        for (int i = (int)digits.size() - 1; i >= 0; i--) {
            if (digits[i] != other.digits[i]) {
                return digits[i] < other.digits[i];
            }
        }
        return false;
    }

    void print() const {
        for (int i = (int)digits.size() - 1; i >= 0; i--) {
            cout << digits[i];
        }
    }
};

int main() {
    int n;
    if (!(cin >> n)) return 0;

    int kingLeft, kingRight;
    cin >> kingLeft >> kingRight;

    vector<Minister> ministers(n);
    for (int i = 0; i < n; i++) {
        cin >> ministers[i].left >> ministers[i].right;
    }

    sort(ministers.begin(), ministers.end(), cmp);

    BigInt product(kingLeft);
    BigInt maxReward(0);

    for (int i = 0; i < n; i++) {
        BigInt reward = product.divide(ministers[i].right);
        if (maxReward.lessThan(reward)) {
            maxReward = reward;
        }
        product = product.multiply(ministers[i].left);
    }

    maxReward.print();
    cout << endl;

    return 0;
}

九、雇佣计划

问题描述 经理需要确定每个月雇佣的工人数，已知每月最少需要的工人数。 * 雇佣新工人费用为 $h$/人，解雇工人费用为 $f$/人。 * 工人在职期间，即使不干活也需要支付工资 $s$/月/人。求 $n$ 个月控制总费用的最低方案。

9.1 问题分析与贪心思想

当月实际工人数 now 必须满足当月最小需求 need[i]。

若人数不足 (need[i] > now)：必须新雇佣 $need[i] - now$ 人，使人数恰好达到最低限度。
若人数多余 (need[i] < now)：是否立即解雇多余的工人？
考虑：如果未来几个月内还需要同样多的人手，解雇后再重新雇佣的费用 $f + h$ 可能大于维持多余人手所支付的额外工资。
贪心策略：向后搜索未来月份。若保留这些人付出的额外工资，小于解雇并重新雇佣的费用，则选择不解雇，维持当前人数。

9.2 C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    int h, s, f;
    cin >> h >> s >> f;

    vector<int> need(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> need[i];
    }

    int mincost = 0;
    int now = 0;

    for (int i = 1; i <= n; i++) {
        if (need[i] > now) {
            // 人手不足，必须雇佣
            mincost += h * (need[i] - now);
            now = need[i];
        } else if (need[i] < now) {
            // 人手多余，决策是否解雇
            bool keep = false;
            for (int j = i + 1; j <= n; j++) {
                if (need[j] >= now) {
                    keep = true;
                    break;
                }
                if (need[j] >= need[i]) {
                    // 额外工资总额 vs 解雇与重新雇佣成本
                    int extraWage = s * (j - i) * (now - need[j]); 
                    int costFireHire = (f + h) * (now - need[j]);
                    if (costFireHire > extraWage) {
                        keep = true;
                        break;
                    }
                }
            }
            if (!keep) {
                // 解雇多余人手至当月最低限度
                mincost += f * (now - need[i]);
                now = need[i];
            }
        }
        mincost += now * s; // 支付当月工资
    }

    cout << mincost << endl;
    return 0;
}

十、贪心算法在树和图论中的应用

图论中许多经典的高效算法都深度应用了贪心思想。

10.1 最小生成树 (MST)

Prim 算法：从任意顶点开始逐步向外扩展树。每一步选择一条连接树内顶点与树外顶点中权重最小的边。
Kruskal 算法：将所有边按权重从小到大排序，每次选择不与已选边构成环的权值最小的边。

// Kruskal 算法核心贪心选择
sort(edges.begin(), edges.end(), cmp);
for (Edge e : edges) {
    int fu = find(e.u), fv = find(e.v);
    if (fu != fv) {
        parent[fu] = fv;
        ans += e.w;
        cnt++;
        if (cnt == n - 1) break;
    }
}

10.2 单源最短路径 (Dijkstra 算法)

用于求解无负权图的单源最短路径。 * 贪心策略：每次从未确定最短路径的节点中，选择一个当前距离源点最近的节点 $u$，加入已确定集合，并用它更新相邻节点的距离（松弛操作）。

// Dijkstra 算法核心贪心选择
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> dist(n+1, INF);
dist[s] = 0;
pq.push({0, s});

while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w] : g[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

十一、小结

11.1 贪心算法的基本要素

贪心选择性质：可以通过一系列局部最优决策达到全局最优。
最优子结构性质：问题的最优解包含其子问题的最优解。

11.2 证明方法

由于贪心策略往往伴随着直觉，在设计出算法后，通常需要进行合理性证明： * 交换论证法：假设存在一个最优解，证明将其中的非贪心决策替换为贪心决策后，解不会变差。 * 数学归纳法：适用于阶段性递推明显的问题。 * 反例构造法：在思考贪心准则时，多尝试构造小规模的极限数据来推翻错误的直觉。

11.3 常见贪心模型与策略总结

经典题型	贪心决策
区间调度（选最多不相交区间）	按右端点升序排序，每次选最早结束的
区间覆盖（用最少区间覆盖目标）	按左端点升序排序，每次选能延伸最远的
排队等待时间最小	按处理/服务时间升序排序
删数问题	从左往右，删去第一个下降趋势的前驱数字
哈夫曼编码（合并果子）	每次选择权值最小的两堆进行合并
部分背包问题	按单位重量的价值（性价比）降序选择
国王游戏	按 $a_i \times b_i$（左手 $\times$ 右手）升序排序

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com