# 贪心与其它模块

---

## 1. 区间问题（以“最大不相交区间数量”为例）

### 数学逻辑与贪心证明
* **问题**：给定 $n$ 个闭区间 $[a_i, b_i]$，选出最多的互不相交区间。
* **贪心策略**：按**右端点 $b_i$ 从小到大**排序，依次选择。
* **直观证明（反证法）**：
  假设按右端点排序后的第一个区间是 $I_1$，其右端点为 $b_1$。如果我们不选 $I_1$ 而去选另一个与 $I_1$ 有交集的区间 $I'$（其右端点 $b' > b_1$），由于 $b_1 \le b'$，选择 $I_1$ 给后续区间留下的剩余空间一定**大于或等于**选择 $I'$ 留下的空间。因此，优先选右端点最小的区间贪心策略永远是最优或至少不比其他策略差。

### C++ 代码模板
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Range {
    int l, r;
    // 重载小于号，按右端点从小到大排序
    bool operator< (const Range &W) const {
        return r < W.r;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Range> ranges;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        ranges.push_back({l, r});
    }

sort(ranges.begin(), ranges.end());

int cnt = 0, ed = -2e9; // ed 记录上一个选定区间的右端点
    for (int i = 0; i < n; i++) {
        if (ranges[i].l > ed) { // 如果当前区间的左端点严格大于上一个的右端点
            cnt++;
            ed = ranges[i].r;   // 更新右端点
        }
    }

cout << cnt << endl;
    return 0;
}
```

---

## 2. Huffman 树 (哈夫曼树)

### 数学公式与 WPL 定义
* **带权路径长度 (WPL)**：设叶子节点的权值为 $w_i$，该节点到根节点的边数为 $l_i$，则整棵树的 WPL 计算公式为：
  $$\text{WPL} = \sum_{i=1}^{n} w_i \cdot l_i$$
* **核心性质**：权值越大的叶子节点，深度越浅（即 $l_i$ 越小），从而使得总加权路径最短。

### C++ 代码模板（利用优先队列/小根堆实现）
```cpp
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> heap; // 小根堆
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        heap.push(x);
    }

int res = 0;
    while (heap.size() > 1) {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;           // 每次合并产生的新权值累加到总代价中
        heap.push(a + b);       // 将新节点放回堆中
    }

cout << res << endl;
    return 0;
}
```

---

## 3. 排序不等式 (Sorting Inequality)

### 数学定理与证明
* **定理表述**：设两组实数 $a_1 \le a_2 \le \dots \le a_n$ 和 $b_1 \le b_2 \le \dots \le b_n$。
  * **顺序和最小**：$\sum a_i b_i$ 在同向排序时达到极小。
  * **乱序和任意**：如果打乱顺序，其和通常变大；反向排序（一升一降）时达到极大。
* **数学证明（微调法/邻项交换法）**：
  假设存在某对相邻的指标 $j$ 和 $j+1$，满足 $a_j \le a_{j+1}$，但 $b_j > b_{j+1}$。
  如果我们把它们的顺序交换，差值为：
  $$\Delta = (a_j b_{j+1} + a_{j+1} b_j) - (a_j b_j + a_{j+1} b_{j+1}) = (a_{j+1} - a_j)(b_j - b_{j+1})$$
  因为 $a_{j+1} \ge a_j$ 且 $b_j \ge b_{j+1}$，所以 $\Delta \le 0$。这说明**逆序的乘积和总是不大于同向排序的乘积和**。反之，同向排序时乘积和最小。

### C++ 代码模板（经典排队打水问题）
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

// 从小到大排序（排序不等式应用：时间短的人先接水）
    sort(t.begin(), t.end());

long long res = 0;
    for (int i = 0; i < n; i++) {
        res += (n - i - 1) * t[i]; // 第 i 个人会被后面 (n - i - 1) 个人等待
    }

cout << res << endl;
    return 0;
}
```

---

## 4. 绝对值不等式 (Absolute Value Inequality)

### 数学原理与推导
* **问题**：求一点 $x$，使得 $\sum_{i=1}^{n} |x - x_i|$ 最小。
* **数学推导（基于绝对值的几何意义）**：
  设数轴上有两个点 $x_1$ 和 $x_2$（且 $x_1 \le x_2$）。当 $x$ 落在区间 $[x_1, x_2]$ 之间时：
  $$|x - x_1| + |x - x_2| = x - x_1 + x_2 - x = x_2 - x_1$$
  这个距离和是一个**恒定常数**。但如果 $x$ 跑到了区间外面（比如 $x < x_1$），距离和会随着 $x$ 远离而不断增大。
  推广到 $n$ 个点：将所有点排序后，两两配对（最小的配最大的，次小的配次大的），它们共同产生的距离下限由中间的点决定。因此，**中位数**就是让总距离最小的唯一（或区间）最优解。

### C++ 代码模板（货仓选址问题）
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

// 排序
    sort(a.begin(), a.end());

// 仓库选在中位数位置 a[n / 2] 距离之和最小
    long long res = 0;
    for (int i = 0; i < n; i++) {
        res += abs(a[i] - a[n / 2]);
    }

cout << res << endl;
    return 0;
}
```

贪心与其它模块

1. 区间问题（以“最大不相交区间数量”为例）

数学逻辑与贪心证明

问题：给定 $n$ 个闭区间 $[a_i, b_i]$，选出最多的互不相交区间。
贪心策略：按右端点 $b_i$ 从小到大排序，依次选择。
直观证明（反证法）：假设按右端点排序后的第一个区间是 $I_1$，其右端点为 $b_1$。如果我们不选 $I_1$ 而去选另一个与 $I_1$ 有交集的区间 $I'$（其右端点 $b' > b_1$），由于 $b_1 \le b'$，选择 $I_1$ 给后续区间留下的剩余空间一定大于或等于选择 $I'$ 留下的空间。因此，优先选右端点最小的区间贪心策略永远是最优或至少不比其他策略差。

C++ 代码模板

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Range {
    int l, r;
    // 重载小于号，按右端点从小到大排序
    bool operator< (const Range &W) const {
        return r < W.r;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Range> ranges;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        ranges.push_back({l, r});
    }

    sort(ranges.begin(), ranges.end());

    int cnt = 0, ed = -2e9; // ed 记录上一个选定区间的右端点
    for (int i = 0; i < n; i++) {
        if (ranges[i].l > ed) { // 如果当前区间的左端点严格大于上一个的右端点
            cnt++;
            ed = ranges[i].r;   // 更新右端点
        }
    }

    cout << cnt << endl;
    return 0;
}

2. Huffman 树 (哈夫曼树)

数学公式与 WPL 定义

带权路径长度 (WPL)：设叶子节点的权值为 $w_i$，该节点到根节点的边数为 $l_i$，则整棵树的 WPL 计算公式为： $$\text{WPL} = \sum_{i=1}^{n} w_i \cdot l_i$$
核心性质：权值越大的叶子节点，深度越浅（即 $l_i$ 越小），从而使得总加权路径最短。

C++ 代码模板（利用优先队列/小根堆实现）

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> heap; // 小根堆
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1) {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;           // 每次合并产生的新权值累加到总代价中
        heap.push(a + b);       // 将新节点放回堆中
    }

    cout << res << endl;
    return 0;
}

3. 排序不等式 (Sorting Inequality)

数学定理与证明

定理表述：设两组实数 $a_1 \le a_2 \le \dots \le a_n$ 和 $b_1 \le b_2 \le \dots \le b_n$。
顺序和最小：$\sum a_i b_i$ 在同向排序时达到极小。
乱序和任意：如果打乱顺序，其和通常变大；反向排序（一升一降）时达到极大。
数学证明（微调法/邻项交换法）：假设存在某对相邻的指标 $j$ 和 $j+1$，满足 $a_j \le a_{j+1}$，但 $b_j > b_{j+1}$。如果我们把它们的顺序交换，差值为： $$\Delta = (a_j b_{j+1} + a_{j+1} b_j) - (a_j b_j + a_{j+1} b_{j+1}) = (a_{j+1} - a_j)(b_j - b_{j+1})$$ 因为 $a_{j+1} \ge a_j$ 且 $b_j \ge b_{j+1}$，所以 $\Delta \le 0$。这说明逆序的乘积和总是不大于同向排序的乘积和。反之，同向排序时乘积和最小。

C++ 代码模板（经典排队打水问题）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    // 从小到大排序（排序不等式应用：时间短的人先接水）
    sort(t.begin(), t.end());

    long long res = 0;
    for (int i = 0; i < n; i++) {
        res += (n - i - 1) * t[i]; // 第 i 个人会被后面 (n - i - 1) 个人等待
    }

    cout << res << endl;
    return 0;
}

4. 绝对值不等式 (Absolute Value Inequality)

数学原理与推导

问题：求一点 $x$，使得 $\sum_{i=1}^{n} |x - x_i|$ 最小。
数学推导（基于绝对值的几何意义）：设数轴上有两个点 $x_1$ 和 $x_2$（且 $x_1 \le x_2$）。当 $x$ 落在区间 $[x_1, x_2]$ 之间时： $$|x - x_1| + |x - x_2| = x - x_1 + x_2 - x = x_2 - x_1$$ 这个距离和是一个恒定常数。但如果 $x$ 跑到了区间外面（比如 $x < x_1$），距离和会随着 $x$ 远离而不断增大。推广到 $n$ 个点：将所有点排序后，两两配对（最小的配最大的，次小的配次大的），它们共同产生的距离下限由中间的点决定。因此，中位数就是让总距离最小的唯一（或区间）最优解。

C++ 代码模板（货仓选址问题）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // 排序
    sort(a.begin(), a.end());

    // 仓库选在中位数位置 a[n / 2] 距离之和最小
    long long res = 0;
    for (int i = 0; i < n; i++) {
        res += abs(a[i] - a[n / 2]);
    }

    cout << res << endl;
    return 0;
}

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