第六讲 · 贪心算法原创

第六讲 · 贪心算法 Banner

AcWing 算法基础课 Banner

第六讲 · 贪心算法 - Soft Blush

AcWing 算法基础课 - Soft Blush

第六讲 · 贪心算法 Banner

AcWing 算法基础课 Banner

第六讲 · 贪心算法 Banner

AcWing 算法基础课 Banner

"The greedy algorithm is a good algorithm to talk about because it is easy to understand, and it is easy to implement, but it is a perfect example of a case where you have to prove that it is correct." -- Thomas H. Cormen
本笔记为 第六讲 · 贪心算法 的 C++ 模板与题解，内容涵盖区间贪心、排序策略、Huffman树、以及多种基于不等式和邻项交换证明的经典贪心模型。
贪心算法，一种在算法世界中追求“眼前最优”的智慧。它不着眼于全局的复杂算计，而是专注于在每个决策点上做出当下看来最好的选择。这种简洁而强大的思想，常常能为复杂问题提供出人意料的高效解法。本章将带你深入探索贪心策略的奥秘，从经典的区间问题到精巧的排序模型，学习如何识别贪心性质，并用代码将这种“局部最优”的智慧转化为通往“全局最优”的捷径。[胭脂水色]

💰 第六讲贪心算法

🧠 1. 贪心算法基础

🎯 1.1 核心思想

贪心算法（Greedy Algorithm）在求解问题时，并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。也就是说，不追求长远，只顾“眼前利益”。其核心是：

局部最优：在问题的每个阶段，都选择当前状态下的最优解。
全局最优：期望通过一系列的局部最优选择，最终能够得到问题的全局最优解。

这种算法思想简单、直观且高效，但其正确性需要严格的证明。

✅ 1.2 适用条件

并非所有问题都能用贪心算法解决。一个问题能使用贪心算法求解，通常需要满足以下两个性质：

贪心选择性质（Greedy Choice Property）： 通过局部最优的选择，不会破坏全局最优解的构建，即局部最优解可以构成全局最优解的一部分。
最优子结构（Optimal Substructure）： 问题的最优解可以通过其子问题的最优解来构造，即问题可以被分解为互不相干的子问题，并且其最优解包含子问题的最优解。

🪜 1.3 设计步骤

设计一个贪心算法通常遵循以下步骤：

问题建模： 明确问题的输入、输出以及需要达到的最优目标。
证明贪心选择性质： 分析问题，证明每次局部选择不会影响全局最优性。如果没有这一步，贪心算法可能只得到一个次优解。
建立排序或优先级结构： 贪心算法常常需要先将数据按照某种关键指标排序（例如活动选择问题中按结束时间排序），或者使用优先队列来动态选择最佳候选。
设计循环结构： 遍历数据，根据贪心策略判断是否选择某个元素，并更新状态。
返回结果： 将构造的解返回，同时分析时间复杂度与空间复杂度。

下面是一些经典贪心模型与实例。

📏 2. 区间问题

区间问题是贪心算法的经典应用场景，通常需要对区间的某个端点进行排序。

📍 2.1 区间选点

🗂️ 2.1.1 洛谷 & 牛客题单

来源	题目/题单	说明
洛谷	https://www.luogu.com.cn/problem/U248666	U248666 区间选点
洛谷	https://www.luogu.com.cn/problem/U380776	U380776 区间选点
洛谷	https://www.luogu.com.cn/problem/T464757	T464757 区间选点问题
洛谷	https://www.luogu.com.cn/problem/T355666	T355666 【5-2练习B】区间选点问题
洛谷	https://www.luogu.com.cn/problem/T505759	T505759 区间选点
洛谷	https://www.luogu.com.cn/problem/U207087	U207087 练习-区间选点问题
洛谷	https://www.luogu.com.cn/problem/U336172	U336172 区间选点
洛谷	https://www.luogu.com.cn/problem/U212594	U212594 区间选点
洛谷	https://www.luogu.com.cn/problem/U183399	U183399 [YBT] 整数区间\|区间选点

❓💡2.1.2 问题和解法

问题描述
给定 N 个闭区间 [a_i, b_i]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。

（1）贪心策略

1、将所有区间按照 右端点 b_i 从小到大排序。

2、遍历排序后的区间：

选择第一个区间的右端点作为第一个点。

对于后续区间，如果它的左端点 a_i 大于上一个选定点的坐标，说明当前区间未被覆盖，此时需要选择当前区间的右端点作为新的点。

（2）证明：选择右端点作为新的选点，是因为它最有可能覆盖到后续更多的区间，从而使得总选点数最少。

（3）代码实现

写法1：按右端点升序

c++

// 闭区间，按右端点从小到大排序
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Range {
  int l, r;
  bool operator<(const Range& t) const {
    return r < t.r;  // 按右端点从小到大排序
  }
} range[N];
int n;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d%d", &range[i].l, &range[i].r);
  sort(range, range + n);

  int ans = 0, lastR = -2e9;  // lastR 记录上一次已经选中的最右端点
  for (int i = 0; i < n; ++i) {
    if (lastR < range[i].l) {
      ++ans;
      lastR = range[i].r;
    }
  }

  printf("%d\n", ans);
  return 0;
}

写法2：按左端点降序（对称操作）

c++

// 按左端点从大到小排序
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Range {
  int l, r;
  bool operator<(const Range& t) const {
    return l > t.l;  // 按左端点从大到小排序
  }
} range[N];
int n;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d%d", &range[i].l, &range[i].r);
  sort(range, range + n);
  // lastL记录上次已经选中的最左端点
  int ans = 0, lastL = 2e9;
  for (int i = 0; i < n; ++i) {
    if (lastL > range[i].r) {
      ++ans;
      lastL = range[i].l;
    }
  }
  printf("%d\n", ans);
  return 0;
}

📈 2.2 最大不相交区间数量

🗂️ 2.2.1 洛谷 & 牛客题单

来源	题目/题单	说明
洛谷	https://www.luogu.com.cn/problem/U248675	U248675 最大不相交区间数量
洛谷	https://www.luogu.com.cn/problem/T642681	T642681 【模板】区间最大不相交问题
洛谷	https://www.luogu.com.cn/problem/U238066	U238066 最大不相交区间数量
洛谷	https://www.luogu.com.cn/problem/U380775	U380775 区间最大不相交问题
洛谷	https://www.luogu.com.cn/problem/U212595	U212595 最大不相交区间数量
洛谷	https://www.luogu.com.cn/problem/T505760	T505760 最大不相交区间数量
洛谷	https://www.luogu.com.cn/problem/U336178	U336178 最大不相交区间数量
洛谷	https://www.luogu.com.cn/problem/P1803	P1803 凌乱的yyy / 线段覆盖

❓💡2.2.2 问题和解法

问题描述
给定 N 个闭区间 [a_i, b_i]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。输出可选取区间的最大数量。

（1）贪心策略 此问题的贪心策略与 区间选点 完全一致。

将所有区间按照 右端点 b_i 从小到大排序。

选择第一个区间，然后遍历后续区间，如果当前区间的左端点 a_i 大于已选区间的最后一个的右端点，则选择当前区间。

（2）证明：每次选择右端点最小的区间，可以为后续留下尽可能多的“空闲”空间，从而容纳更多的区间。

（3）代码实现

（代码与“区间选点”问题完全相同）

c++

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

const int N = 1e5 + 10;
struct Range {
  int l, r;
  bool operator<(const Range& t) const {
    return r < t.r; // 按右端点从小到大排序
  }
} range[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &range[i].l, &range[i].r);
  }
  sort(range, range + n);

  int ans = 0;
  int lastR = -2e9; // 记录上一个选中区间的右端点
  for (int i = 0; i < n; ++i) {
    if (range[i].l > lastR) {
      ans++;
      lastR = range[i].r;
    }
  }

  printf("%d\n", ans);
  return 0;
}

📦 2.3 区间分组

🗂️ 2.3.1 洛谷 & 牛客题单

来源	题目/题单	说明
洛谷	https://www.luogu.com.cn/problem/U248679	U248679 区间分组
洛谷	https://www.luogu.com.cn/problem/T533921	T533921 区间分组
洛谷	https://www.luogu.com.cn/problem/U492913	U492913 区间分组
洛谷	https://www.luogu.com.cn/problem/U380779	U380779 区间分组
洛谷	https://www.luogu.com.cn/problem/T664751	T664751 区间分组
洛谷	https://www.luogu.com.cn/problem/U336186	U336186 区间分组
洛谷	https://www.luogu.com.cn/problem/U212597	U212597 区间分组
洛谷	https://www.luogu.com.cn/problem/P2434	P2434 [SDOI2005] 区间

❓💡2.3.2 问题和解法

问题描述
给定 N 个闭区间 [a_i, b_i]，请你将这些区间分成若干组，使得每组内部的区间两两之间没有交集，并使得组数尽可能小。输出最小组数。

（1）贪心策略

1、将所有区间按照 左端点 a_i 从小到大排序。

2、维护一个存储各组当前最右端点的小根堆。

3、遍历排序后的区间：

如果当前区间的左端点 a_i 大于堆顶元素（即某一组的最右端点），说明可以将该区间放入该组。更新该组的最右端点（弹出堆顶，压入当前区间的右端点 b_i）。

否则，当前区间无法放入任何现有组，必须开一个新组。将该区间的右端点 b_i 压入堆中。

4、最终堆的大小即为最小组数。

（2）代码实现

c++

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
struct Range {
  int l, r;
  bool operator<(const Range& t) const { return l < t.l; }
} range[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) { scanf("%d%d", &range[i].l, &range[i].r); }
  sort(range, range + n);

  priority_queue<int, vector<int>, greater<int>>pq;  // 小根堆，存储每组最右端点
  for (int i = 0; i < n; ++i) {
    if (pq.empty() || range[i].l <= pq.top()) {
      // 开新组
      pq.push(range[i].r);
    } else {
      // 放入现有组
      pq.pop();
      pq.push(range[i].r);
    }
  }

  printf("%d\n", pq.size());
  return 0;
}

🧩 2.4 区间覆盖

🗂️ 2.4.1 洛谷 & 牛客题单

来源	题目/题单	说明
洛谷	https://www.luogu.com.cn/problem/U248682	U248682 区间覆盖
洛谷	https://www.luogu.com.cn/problem/U380778	U380778 区间覆盖
洛谷	https://www.luogu.com.cn/problem/U492914	U492914 区间覆盖
洛谷	https://www.luogu.com.cn/problem/T664753	T664753 区间覆盖
洛谷	https://www.luogu.com.cn/problem/U310416	U310416 区间覆盖
洛谷	https://www.luogu.com.cn/problem/U207088	U207088 区间覆盖问题
洛谷	https://www.luogu.com.cn/problem/U236112	U236112 【贪心】区间线段覆盖问题
洛谷	https://www.luogu.com.cn/problem/P2082	P2082 区间覆盖（加强版）
洛谷	https://www.luogu.com.cn/problem/U430784	U430784 区间覆盖究极加强版

❓💡2.4.2 问题和解法

问题描述
给定 N 个闭区间 [a_i, b_i] 以及一个线段区间 [s, t]，请你选择尽量少的区间，将指定线段区间完全覆盖。输出最少区间数，如果无法完全覆盖则输出 -1。

（1）贪心策略

1、将所有区间按照 左端点 a_i 从小到大排序。

2、设当前已覆盖区间的右端点为 start（初始为 s）。

3、在所有左端点 a_i <= start 的区间中，选择一个 右端点最大 的区间 [a_j, b_j]。

4、将 start 更新为 b_j，计数器加一。

5、重复步骤 3 和 4，直到 start >= t。如果在某一步中找不到满足条件的区间，则无解。

（2）代码实现

c++

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Range {
  int l, r;
  bool operator<(const Range& t) const { return l < t.l; }
} range[N];

int main() {
  int s, t, n;
  scanf("%d%d", &s, &t);
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) { scanf("%d%d", &range[i].l, &range[i].r); }
  sort(range, range + n);

  int ans = 0;
  bool success = false;
  for (int i = 0; i < n; ++i) {
    int j = i, max_r = -2e9;
    // 在所有能覆盖当前 s 点的区间里，找右端点最远的
    while (j < n && range[j].l <= s) {
      max_r = max(max_r, range[j].r);
      j++;
    }

    if (max_r < s) {  // 找不到能覆盖 s 的区间
      ans = -1;
      break;
    }

    ans++;
    if (max_r >= t) {  // 成功覆盖
      success = true;
      break;
    }

    s = max_r; // 更新起点
    i = j - 1; // 更新i到检查过的位置
  }

  if (!success) ans = -1;
  printf("%d\n", ans);
  return 0;
}

🌳 3. Huffman 树模型

Huffman 树是贪心思想的完美体现，常用于解决“合并代价”最小化问题。

🍎 3.1 合并果子

🗂️ 3.1.1 洛谷 & 牛客题单

来源	题目/题单	说明
洛谷	https://www.nowcoder.com/practice/854e7118eb08464ab8ce7a0bca8b276c	合并果子
洛谷	https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155	哈夫曼树
洛谷	https://www.luogu.com.cn/problem/P1090	P1090 [NOIP 2004 提高组] 合并果子
洛谷	https://www.luogu.com.cn/problem/T685337	T685337 合并果子
洛谷	https://www.luogu.com.cn/problem/U530232	U530232 [Luke_xiao round 1] 合并果子
洛谷	https://www.luogu.com.cn/problem/T574557	T574557 [NOIP 2004 提高组] 合并果子
洛谷	https://www.luogu.com.cn/problem/T508078	T508078 【5-2练习C】合并果子
洛谷	https://www.luogu.com.cn/problem/P6033	P6033 [NOIP 2004 提高组] 合并果子加强版（普及+/提高）
洛谷	https://www.luogu.com.cn/training/498220	哈夫曼树（题单）
洛谷	https://www.luogu.com.cn/training/243380	【Tea徐】入门组训练（哈夫曼树）（题单）
洛谷	https://www.luogu.com.cn/training/507114	二叉树和哈夫曼树（题单）
洛谷	https://www.luogu.com.cn/training/468140	哈夫曼树(S组)（题单）

❓💡3.1.2 问题和解法

问题描述 (P1090 [NOIP 2004 提高组] 合并果子)
有 n 堆果子，每堆的果子数量已知。每次可以合并任意两堆果子，消耗的体力等于两堆果子的数量之和。经过 n-1 次合并后，所有果子会变成一堆。求耗费的体力总和的最小值。

（1）贪心策略 要使总代价最小，每次应选择当前数量最少的两堆果子进行合并。因为数量少的果子在合并树的底层，它们被计算的次数（深度）最多，将小数放在底层能使总和最小。这正是 Huffman 树 的构造过程。

1、使用小根堆维护所有果子堆。

2、循环 n-1 次：

从堆中取出最小的两个数 x 和 y。

将它们的和 x+y 累加到总代价中。

将新堆 x+y 重新放入小根堆。

3、最终累加的代价即为最小体力耗费。

（2）代码实现

c++

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

int main() {
  scanf("%d", &n);
  priority_queue<int, vector<int>, greater<int>> q;
  while (n--) {
    int x;
    scanf("%d", &x);
    q.push(x);
  }

  int ans = 0;
  while (q.size() > 1) {
    int x = q.top();
    q.pop();
    int y = q.top();
    q.pop();
    ans += x + y;
    q.push(x + y);
  }

  printf("%d\n", ans);
  return 0;
}

⚖️ 4. 排序不等式模型

排序不等式指出，顺序和 ≥ 乱序和 ≥ 逆序和。利用此性质可以解决一些与求和最小/最大相关的问题。

💧 4.1 排队打水

🗂️ 4.1.1 洛谷 & 牛客题单

来源	题目/题单	说明
洛谷	https://www.luogu.com.cn/problem/P1223	P1223 排队接水
洛谷	https://www.luogu.com.cn/problem/U235350	U235350 排队接水
洛谷	https://www.luogu.com.cn/problem/U283548	U283548 【贪心】接水问题

❓💡4.1.2 问题和解法

问题描述 (P1223 排队接水)
有 n 个人排队接水，每个人接水的时间为 T_i。请安排一个顺序，使得所有人的 总等待时间 最小。

（1）贪心策略 总等待时间 = 0 + T_1 + (T_1+T_2) + ... + (T_1+...+T_{n-1}) 整理后可得 = (n-1)T_1 + (n-2)T_2 + ... + 1*T_{n-1} 根据排序不等式，要使这个和最小，应该让较小的 T_i 乘以较大的系数 (n-i)。因此，贪心策略是：让接水时间短的人排在前面。

1、将每个人的接水时间 T_i 从小到大排序。

2、按排序后的顺序计算总等待时间。

（2）代码实现

c++

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

const int N = 1005;
struct Person {
    int id;
    int time;
    bool operator<(const Person& other) const {
        return time < other.time;
    }
} p[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        p[i].id = i;
        scanf("%d", &p[i].time);
    }

    sort(p + 1, p + 1 + n);

    long long total_wait_time = 0;
    long long current_time = 0;
    for (int i = 1; i < n; ++i) {
        printf("%d ", p[i].id);
        current_time += p[i].time;
        total_wait_time += current_time;
    }
    printf("%d\n", p[n].id);

    printf("%.2f\n", (double)total_wait_time / n);
    return 0;
}

注：原题要求输出平均等待时间，但最小化总等待时间等价于最小化平均等待时间。

🏠 5. 绝对值不等式模型

形如 $\sum | x - a_{i} |$ 的式子，其几何意义是数轴上一点 x 到若干点 a_i 的距离之和。

🏭 5.1 货仓选址

🗂️ 5.1.1 洛谷 & 牛客题单

来源	题目/题单	说明
牛客	https://www.nowcoder.com/practice/4938eb9320214ff48583e87bcf4db15e	仓库选址
洛谷	https://www.luogu.com.cn/problem/P10452	P10452 货仓选址
洛谷	https://www.luogu.com.cn/problem/T507182	T507182 货仓选址
洛谷	https://www.luogu.com.cn/problem/U208125	U208125 货仓选址
洛谷	https://www.luogu.com.cn/problem/U216784	U216784 货仓选址
洛谷	https://www.luogu.com.cn/problem/T445072	T445072 货仓选址
洛谷	https://www.luogu.com.cn/problem/U270934	U270934 货仓选址
洛谷	https://www.luogu.com.cn/problem/U167449	U167449 货仓选址
洛谷	https://www.luogu.com.cn/problem/T663533	T663533 作业题：货仓选址
洛谷	https://www.luogu.com.cn/problem/U212641	U212641 货仓选址
洛谷	https://www.luogu.com.cn/problem/T551808	T551808 货仓选址(12-15)
洛谷	https://www.luogu.com.cn/problem/T516247	T516247 货仓选址
洛谷	https://www.luogu.com.cn/problem/U186336	U186336 选址
洛谷	https://www.luogu.com.cn/problem/T508088	T508088 【5-1例题C】货仓选址
洛谷	https://www.luogu.com.cn/problem/U587418	U587418 0x05 货仓选址
洛谷	https://www.luogu.com.cn/problem/U520107	U520107 货仓选址
洛谷	https://www.luogu.com.cn/problem/T446368	T446368 货仓选址

❓💡5.1.2 问题和解法

问题描述
在一条数轴上有 N 家商店，坐标分别为 A_1, ..., A_N。需要在数轴上建立一家货仓，使得货仓到每家商店的距离之和最小。求这个最小距离和。

（1）贪心策略 问题是找到一个点 x，最小化 Σ|x - A_i|。根据绝对值不等式的结论，当 x 选在所有坐标 A_i 的 中位数 时，该距离和最小。

1、将所有商店的坐标 A_i 排序。

2、选择中位数 A[n/2] 作为货仓位置。

3、计算所有商店到该中位数的距离之和。

（2）代码实现

c++

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

const int N = 1e5 + 10;
int a[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a, a + n);

  int median_pos = a[n / 2];
  long long sum_dist = 0;
  for (int i = 0; i < n; ++i) {
    sum_dist += abs(a[i] - median_pos);
  }

  printf("%lld\n", sum_dist);
  return 0;
}

🤝 6. 推公式（邻项交换证明模型）

对于一些排序贪心问题，其排序依据不直观，常通过“邻项交换法”（或称“微扰法”）来证明其正确性。

🐄 6.1 耍杂技的牛

🗂️ 6.1.1 洛谷 & 牛客题单

来源	题目/题单	说明
洛谷	https://www.luogu.com.cn/problem/P1842	P1842 [USACO05NOV] 奶牛玩杂技
洛谷	https://www.luogu.com.cn/problem/T508090	T508090 【5-2例题A】奶牛玩杂技

❓💡6.1.2 问题和解法

问题描述 (P1842 [USACO05NOV] 奶牛玩杂技)
N 头牛叠罗汉，每头牛有体重 W_i 和力量 S_i。一头牛的压扁指数定义为它上方所有牛的总重减去它的力量。所有牛叠完后，找出所有牛中压扁指数的最大值。要求设计一种顺序，使得这个最大值最小。

（1）贪心策略 考虑任意相邻的两头牛 i 和 j，假设 i 在 j 上方。

j 的压扁指数为 ... + W_i - S_j，i 的压扁指数为 ... - S_i。

如果交换它们，j 在 i 上方：

i 的压扁指数为 ... + W_j - S_i，j 的压扁指数为 ... - S_j 比较交换前后的压扁指数最大值，可以发现，为了使最大值更小，应该满足 W_i + S_i < W_j + S_j 的牛排在上方。因此，贪心策略是：将所有牛按照 W_i + S_i 的和从小到大排序。

（2）代码实现

c++

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

using namespace std;
const int N = 50010;

struct Cow {
  int w, s;
};

bool compareCows(const Cow& a, const Cow& b) {
  return a.w + a.s < b.w + b.s;
}

Cow cows[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &cows[i].w, &cows[i].s);
  }

  sort(cows, cows + n, compareCows);

  long long sum_w = 0;
  long long max_risk = -2e9; // 压扁指数可能为负

  for (int i = 0; i < n; ++i) {
    // 对于第i头牛，它头上的重量是 sum_w
    long long risk = sum_w - cows[i].s;
    max_risk = max(max_risk, risk);
    sum_w += cows[i].w;
  }

  printf("%lld\n", max_risk);
  return 0;
}

第六讲 · 贪心算法 原创 ​

💰 第六讲 贪心算法 ​

🧠 1. 贪心算法基础 ​

🎯 1.1 核心思想 ​

✅ 1.2 适用条件 ​

🪜 1.3 设计步骤 ​

📏 2. 区间问题 ​

📍 2.1 区间选点 ​

🗂️ 2.1.1 洛谷 & 牛客题单 ​

❓💡2.1.2 问题和解法 ​

📈 2.2 最大不相交区间数量 ​

🗂️ 2.2.1 洛谷 & 牛客题单 ​

❓💡2.2.2 问题和解法 ​

📦 2.3 区间分组 ​

🗂️ 2.3.1 洛谷 & 牛客题单 ​

❓💡2.3.2 问题和解法 ​

🧩 2.4 区间覆盖 ​

🗂️ 2.4.1 洛谷 & 牛客题单 ​

❓💡2.4.2 问题和解法 ​

🌳 3. Huffman 树模型 ​

🍎 3.1 合并果子 ​

🗂️ 3.1.1 洛谷 & 牛客题单 ​

❓💡3.1.2 问题和解法 ​

⚖️ 4. 排序不等式模型 ​

💧 4.1 排队打水 ​

🗂️ 4.1.1 洛谷 & 牛客题单 ​

❓💡4.1.2 问题和解法 ​

🏠 5. 绝对值不等式模型 ​

🏭 5.1 货仓选址 ​

🗂️ 5.1.1 洛谷 & 牛客题单 ​

❓💡5.1.2 问题和解法 ​

🤝 6. 推公式（邻项交换证明模型） ​

🐄 6.1 耍杂技的牛 ​

🗂️ 6.1.1 洛谷 & 牛客题单 ​

❓💡6.1.2 问题和解法 ​

第六讲 · 贪心算法原创

💰 第六讲贪心算法

🧠 1. 贪心算法基础

🎯 1.1 核心思想

✅ 1.2 适用条件

🪜 1.3 设计步骤

📏 2. 区间问题

📍 2.1 区间选点

🗂️ 2.1.1 洛谷 & 牛客题单

❓💡2.1.2 问题和解法

📈 2.2 最大不相交区间数量

🗂️ 2.2.1 洛谷 & 牛客题单

❓💡2.2.2 问题和解法

📦 2.3 区间分组

🗂️ 2.3.1 洛谷 & 牛客题单

❓💡2.3.2 问题和解法

🧩 2.4 区间覆盖

🗂️ 2.4.1 洛谷 & 牛客题单

❓💡2.4.2 问题和解法

🌳 3. Huffman 树模型

🍎 3.1 合并果子

🗂️ 3.1.1 洛谷 & 牛客题单

❓💡3.1.2 问题和解法

⚖️ 4. 排序不等式模型

💧 4.1 排队打水

🗂️ 4.1.1 洛谷 & 牛客题单

❓💡4.1.2 问题和解法

🏠 5. 绝对值不等式模型

🏭 5.1 货仓选址

🗂️ 5.1.1 洛谷 & 牛客题单

❓💡5.1.2 问题和解法

🤝 6. 推公式（邻项交换证明模型）

🐄 6.1 耍杂技的牛

🗂️ 6.1.1 洛谷 & 牛客题单

❓💡6.1.2 问题和解法