第三章 排序与贪心¶
本章目标：掌握六种经典排序算法的原理与实现，理解贪心算法的核心思想，并能运用排序 + 贪心策略解决区间调度、分配、跳跃等经典问题。
3.1 排序算法¶
排序是算法竞赛中最基础、最高频的操作之一。本节我们将从最简单的冒泡排序开始，逐步讲解六种经典排序算法。
3.1.1 冒泡排序（Bubble Sort）¶
核心思想：重复遍历数组，每次比较相邻元素，若逆序则交换，像气泡一样把最大元素"浮"到末尾。
graph LR
A["初始: 5 3 8 1"] --> B["第1轮: 3 5 1 8"]
B --> C["第2轮: 3 1 5 8"]
C --> D["第3轮: 1 3 5 8"]代码实现
#include <bits/stdc++.h>
using namespace std;
// 冒泡排序：每次把最大的元素"冒泡"到末尾
void bubbleSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // 优化：若本轮无交换，说明已有序
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 提前终止
}
}
int main() {
vector<int> a = {5, 3, 8, 1, 2};
bubbleSort(a);
for (int x : a) cout << x << " "; // 输出: 1 2 3 5 8
return 0;
}
| 复杂度 | 最好 | 最坏 | 平均 | 空间 |
|---|---|---|---|---|
| 时间 | O(n) | O(n²) | O(n²) | O(1) |
3.1.2 选择排序（Selection Sort）¶
核心思想：每轮从未排序部分选出最小元素，放到已排序部分的末尾。
graph LR
A["初始: 5 3 8 1"] --> B["第1轮: 1 | 3 8 5"]
B --> C["第2轮: 1 3 | 8 5"]
C --> D["第3轮: 1 3 5 | 8"]代码实现
#include <bits/stdc++.h>
using namespace std;
// 选择排序：每轮选出最小元素放到前面
void selectionSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i; // 记录最小值的下标
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx]) minIdx = j;
}
swap(a[i], a[minIdx]); // 把最小值放到位置 i
}
}
int main() {
vector<int> a = {5, 3, 8, 1, 2};
selectionSort(a);
for (int x : a) cout << x << " "; // 输出: 1 2 3 5 8
return 0;
}
| 复杂度 | 最好 | 最坏 | 平均 | 空间 |
|---|---|---|---|---|
| 时间 | O(n²) | O(n²) | O(n²) | O(1) |
选择排序是不稳定的
例如 [5, 8, 5, 2, 9]，第一轮选择 2 与第一个 5 交换后，两个 5 的相对顺序改变了。
3.1.3 插入排序（Insertion Sort）¶
核心思想：将数组分为"已排序"和"未排序"两部分，每次从未排序部分取一个元素，插入到已排序部分的正确位置。类似于打扑克牌时整理手牌。
graph LR
A["初始: 5 3 8 1"] --> B["第1步: 3 5 8 1"]
B --> C["第2步: 3 5 8 1"]
C --> D["第3步: 1 3 5 8"]代码实现
#include <bits/stdc++.h>
using namespace std;
// 插入排序：将当前元素插入到前面已排序部分的正确位置
void insertionSort(vector<int>& a) {
int n = a.size();
for (int i = 1; i < n; i++) {
int key = a[i]; // 当前待插入的元素
int j = i - 1;
// 将比 key 大的元素后移
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key; // 插入到正确位置
}
}
int main() {
vector<int> a = {5, 3, 8, 1, 2};
insertionSort(a);
for (int x : a) cout << x << " "; // 输出: 1 2 3 5 8
return 0;
}
| 复杂度 | 最好 | 最坏 | 平均 | 空间 |
|---|---|---|---|---|
| 时间 | O(n) | O(n²) | O(n²) | O(1) |
插入排序的适用场景
- 数据量小（n < 50）时，插入排序往往比 O(n log n) 的排序更快（常数因子小）
- 数据基本有序时，插入排序接近 O(n)
- STL 中
std::sort在小规模子数组上使用插入排序
3.1.4 归并排序（Merge Sort）¶
核心思想：分治法。将数组从中间分成两半，分别递归排序，然后合并两个有序子数组。
graph TD
A["5 3 8 1 2"] --> B["5 3 8"]
A --> C["1 2"]
B --> D["5 3"]
B --> E["8"]
C --> F["1"]
C --> G["2"]
D --> H["3 5"]
H --> I["合并: 1 2 3 5 8"]
E --> I
F --> I
G --> I代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int a[MAXN], tmp[MAXN]; // 原数组和临时数组
// 归并排序：将 [l, r] 区间排序
void mergeSort(int a[], int l, int r) {
if (l >= r) return; // 递归终止：区间长度 <= 1
int mid = (l + r) / 2;
mergeSort(a, l, mid); // 排序左半部分
mergeSort(a, mid + 1, r); // 排序右半部分
// 合并两个有序子数组
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++]; // 左半剩余
while (j <= r) tmp[k++] = a[j++]; // 右半剩余
// 拷贝回原数组
for (int p = l; p <= r; p++) a[p] = tmp[p];
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
mergeSort(a, 0, n - 1);
for (int i = 0; i < n; i++) cout << a[i] << " ";
return 0;
}
| 复杂度 | 最好 | 最坏 | 平均 | 空间 |
|---|---|---|---|---|
| 时间 | O(n log n) | O(n log n) | O(n log n) | O(n) |
归并排序的优势
- 稳定排序：相等元素的相对位置不变
- 时间稳定：最好、最坏、平均都是 O(n log n)
- 逆序对计数：在合并过程中可以顺便统计逆序对数量
归并排序求逆序对
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int a[MAXN], tmp[MAXN];
long long invCount = 0; // 逆序对数量
void mergeSort(int a[], int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergeSort(a, l, mid);
mergeSort(a, mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
// a[i] > a[j]，说明 a[i..mid] 都与 a[j] 构成逆序对
invCount += (mid - i + 1);
tmp[k++] = a[j++];
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int p = l; p <= r; p++) a[p] = tmp[p];
}
3.1.5 快速排序（Quick Sort）¶
核心思想：选择一个基准元素（pivot），将数组分为"小于 pivot"和"大于 pivot"两部分，然后递归排序。
graph TD
A["5 3 8 1 2, pivot=5"] --> B["3 1 2 | 5 | 8"]
B --> C["排序 3 1 2"]
B --> D["排序 8"]
C --> E["1 2 3"]
E --> F["合并: 1 2 3 5 8"]
D --> F代码实现（挖坑法）
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int a[MAXN];
// 快速排序：对 [l, r] 区间排序
void quickSort(int a[], int l, int r) {
if (l >= r) return;
// 小区间截断：三数取中要求区间长度 >= 3
// 长度为 2 时直接比较交换，否则 a[--j] 会越界读 a[l-1]
if (r - l < 2) {
if (a[l] > a[r]) swap(a[l], a[r]);
return;
}
// 三数取中选 pivot（避免最坏情况）
int mid = (l + r) / 2;
if (a[l] > a[mid]) swap(a[l], a[mid]);
if (a[l] > a[r]) swap(a[l], a[r]);
if (a[mid] > a[r]) swap(a[mid], a[r]);
swap(a[mid], a[r - 1]); // 把 pivot 放到 r-1 位置
int pivot = a[r - 1];
int i = l, j = r - 1;
while (true) {
while (a[++i] < pivot); // 从左找 >= pivot 的
while (a[--j] > pivot); // 从右找 <= pivot 的
if (i < j) swap(a[i], a[j]);
else break;
}
swap(a[i], a[r - 1]); // 把 pivot 放回正确位置
quickSort(a, l, i - 1); // 递归排序左半部分
quickSort(a, i + 1, r); // 递归排序右半部分
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
quickSort(a, 0, n - 1);
for (int i = 0; i < n; i++) cout << a[i] << " ";
return 0;
}
| 复杂度 | 最好 | 最坏 | 平均 | 空间 |
|---|---|---|---|---|
| 时间 | O(n log n) | O(n²) | O(n log n) | O(log n) |
快速排序的注意事项
- 最坏情况 O(n²)：当数组已有序且选首/尾元素为 pivot 时
- 解决方案：随机选 pivot 或三数取中
- 快速排序是不稳定排序
- STL
std::sort底层就是快排的变体（Introsort：快排 + 堆排 + 插入排序）
3.1.6 堆排序（Heap Sort）¶
核心思想：利用堆（完全二叉树）的性质。先建大顶堆，然后反复取出堆顶（最大值）放到末尾。
graph TD
A["建大顶堆"] --> B["交换堆顶与末尾"]
B --> C["堆大小减 1"]
C --> D["调整堆（下沉）"]
D --> B代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int a[MAXN];
int heapSize; // 堆的大小
// 下沉操作：维护大顶堆性质
void siftDown(int i) {
while (2 * i + 1 < heapSize) { // 有左孩子
int child = 2 * i + 1; // 左孩子下标
// 选择左右孩子中较大的
if (child + 1 < heapSize && a[child + 1] > a[child])
child++;
// 如果孩子比父节点大，交换并继续下沉
if (a[child] > a[i]) {
swap(a[i], a[child]);
i = child;
} else {
break;
}
}
}
// 堆排序
void heapSort(int n) {
heapSize = n; // 必须先设置堆大小再建堆（siftDown 依赖 heapSize）
// 第一步：建堆（从最后一个非叶子节点开始下沉）
for (int i = n / 2 - 1; i >= 0; i--)
siftDown(i);
// 第二步：反复取出堆顶
for (int i = n - 1; i > 0; i--) {
swap(a[0], a[i]); // 把堆顶（最大值）放到末尾
heapSize--; // 堆大小减 1
siftDown(0); // 调整堆
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
heapSort(n);
for (int i = 0; i < n; i++) cout << a[i] << " ";
return 0;
}
| 复杂度 | 最好 | 最坏 | 平均 | 空间 |
|---|---|---|---|---|
| 时间 | O(n log n) | O(n log n) | O(n log n) | O(1) |
STL 优先队列
实际竞赛中通常直接使用 std::priority_queue（大顶堆）或 std::priority_queue<int, vector<int>, greater<int>>（小顶堆）。
3.1.7 非比较排序（计数 / 桶 / 基数）¶
前面六种排序都基于元素两两比较，理论下界是 O(n log n)。如果数据本身有额外性质（如都是较小范围内的整数），可以完全不比较元素，利用值域信息直接确定每个元素的位置，突破 O(n log n) 的限制。
graph LR
A["比较排序<br/>下界 O(n log n)"] --> B["利用值域信息"]
B --> C["计数排序 O(n + k)"]
B --> D["桶排序 平均 O(n + k)"]
B --> E["基数排序 O(d(n + b))"]计数排序（Counting Sort）¶
核心思想：统计每个值出现的次数，再按值域顺序依次输出。配合前缀和可以做到稳定排序。
代码实现
#include <bits/stdc++.h>
using namespace std;
// 计数排序：对值域为 [0, maxVal] 的非负整数排序
// 时间 O(n + k)，空间 O(n + k)，k = maxVal + 1 为值域大小
void countingSort(vector<int>& a, int maxVal) {
vector<int> cnt(maxVal + 1, 0);
for (int x : a) cnt[x]++; // 统计每个值出现的次数
for (int v = 1; v <= maxVal; v++) cnt[v] += cnt[v - 1]; // 前缀和：cnt[v] = 值 <= v 的个数
vector<int> res(a.size());
// 从后往前放置，保证相等元素的相对顺序不变（稳定）
for (int i = (int)a.size() - 1; i >= 0; i--)
res[--cnt[a[i]]] = a[i];
a = res;
}
int main() {
vector<int> a = {5, 3, 8, 1, 2, 3, 5};
countingSort(a, 8);
for (int x : a) cout << x << " "; // 输出: 1 2 3 3 5 5 8
return 0;
}
| 复杂度 | 时间 | 空间 | 稳定性 |
|---|---|---|---|
| 计数排序 | O(n + k) | O(n + k) | 稳定 |
桶排序（Bucket Sort）¶
核心思想：把值域均分成若干个"桶"，元素按大小落入对应的桶，桶内单独排序后按桶序拼接。数据均匀分布时每个桶都很小，平均复杂度 O(n + k)；数据全挤在一个桶时退化为桶内排序的复杂度。
// 桶排序：把值域均分成 bucketCnt 个桶，桶内再排序
// 数据均匀分布时平均 O(n + k)，最坏（全挤一个桶）退化
void bucketSort(vector<int>& a, int bucketCnt) {
if (a.empty()) return;
int maxVal = *max_element(a.begin(), a.end());
vector<vector<int>> buckets(bucketCnt);
for (int x : a) // 值越大落入编号越大的桶
buckets[(long long)x * bucketCnt / (maxVal + 1)].push_back(x);
a.clear();
for (auto& b : buckets) {
sort(b.begin(), b.end()); // 桶内排序（数据均匀时每桶很小）
for (int x : b) a.push_back(x);
}
}
基数排序（Radix Sort）¶
核心思想：从最低位（LSD）开始，按"个位 → 十位 → 百位……"依次做一轮稳定的计数排序。低位排好后，高位相同的元素之间保持低位的有序性，全部位处理完即整体有序。
// 基数排序（LSD，按十进制位）：对非负整数排序
// 时间 O(d * (n + 10))，d 为最大数的位数
void radixSort(vector<int>& a) {
if (a.empty()) return;
int maxVal = *max_element(a.begin(), a.end());
vector<int> res(a.size());
for (int exp = 1; maxVal / exp > 0; exp *= 10) { // 依次按个位、十位、百位……
int cnt[10] = {0};
for (int x : a) cnt[x / exp % 10]++;
for (int d = 1; d < 10; d++) cnt[d] += cnt[d - 1];
for (int i = (int)a.size() - 1; i >= 0; i--) // 稳定：从后往前
res[--cnt[a[i] / exp % 10]] = a[i];
a = res;
}
}
复杂度分析：设最大数有 d 位、每位有 b 种取值（十进制 b = 10），则时间 O(d(n + b))，空间 O(n + b)，稳定。
例题：洛谷 P1059 明明的随机数
题意：给定 n（n ≤ 100）个 1 ~ 1000 之间的随机整数，去掉重复的数字并从小到大排序输出（先输出去重后的个数，再输出排好序的数）。
值域只有 1000，用一个 bool 桶数组标记出现过的值，按值域顺序扫一遍即同时完成去重与排序——这正是计数/桶思想的最简形态。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
bool exist[1001] = {false}; // exist[v]：数值 v 是否出现过（桶思想）
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
exist[x] = true; // 同时完成去重
}
int cnt = 0;
for (int v = 1; v <= 1000; v++)
if (exist[v]) cnt++;
cout << cnt << "\n";
for (int v = 1; v <= 1000; v++) // 按值域顺序输出即为有序
if (exist[v]) cout << v << " ";
return 0;
}
非比较排序的适用场景与局限
- 值域必须可控：计数排序的空间是 O(k)，值域到 10^9 时数组根本开不下，此时只能用比较排序或离散化
- 只适合整数（或可映射为整数的键）：浮点数、自定义比较规则无法直接用计数/基数排序
- 负数要平移：计数/基数排序默认处理非负整数，有负数时先整体加上偏移量
- 桶排序怕数据倾斜：分布不均时大量元素落入同一个桶，复杂度退化
- 竞赛中最常见的用法其实是"桶思想"：统计出现次数、按值域枚举，而非完整的排序实现
排序算法总结¶
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学演示 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 教学演示 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小数据 / 基本有序 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 需要稳定性、逆序对 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存受限 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | 稳定 | 整数、值域 k 较小 |
| 桶排序 | O(n + k) | O(n²) | O(n + k) | 取决于桶内排序 | 数据均匀分布 |
| 基数排序 | O(d(n + b)) | O(d(n + b)) | O(n + b) | 稳定 | 整数 / 定长字符串 |
3.2 排序应用¶
3.2.1 自定义比较函数¶
在 C++ 中，我们可以通过自定义比较函数来改变排序规则。
#include <bits/stdc++.h>
using namespace std;
// 定义结构体
struct Student {
string name;
int score;
};
// 方法一：重载 < 运算符
bool operator<(const Student& a, const Student& b) {
if (a.score != b.score) return a.score > b.score; // 分数高的排前面
return a.name < b.name; // 分数相同按名字字典序
}
// 方法二：自定义比较函数
bool cmp(const Student& a, const Student& b) {
if (a.score != b.score) return a.score > b.score;
return a.name < b.name;
}
int main() {
vector<Student> students = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 90}};
// 使用比较函数
sort(students.begin(), students.end(), cmp);
// 使用 lambda 表达式（推荐，更简洁）
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
if (a.score != b.score) return a.score > b.score;
return a.name < b.name;
});
for (auto& s : students)
cout << s.name << " " << s.score << endl;
return 0;
}
3.2.2 sort 高级用法¶
#include <bits/stdc++.h>
using namespace std;
int main() {
// 1. 对 vector 排序
vector<int> v = {3, 1, 4, 1, 5, 9};
sort(v.begin(), v.end()); // 升序: 1 1 3 4 5 9
sort(v.begin(), v.end(), greater<int>()); // 降序: 9 5 4 3 1 1
// 2. 对数组排序
int arr[] = {3, 1, 4, 1, 5, 9};
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n); // 升序
// 3. 部分排序（只排序前 k 个最小元素）
vector<int> a = {5, 3, 8, 1, 9, 2};
nth_element(a.begin(), a.begin() + 2, a.end()); // 第 3 小的元素在正确位置
// a 的前 3 个元素是原数组中最小的 3 个（但不一定有序）
// 4. 判断是否已排序
if (is_sorted(v.begin(), v.end())) {
cout << "已排序" << endl;
}
// 5. 稳定排序（保持相等元素的相对顺序）
stable_sort(v.begin(), v.end());
return 0;
}
3.2.3 排序不等式¶
排序不等式：对于两个同样大小的序列 \(a_1 \le a_2 \le \dots \le a_n\) 和 \(b_1 \le b_2 \le \dots \le b_n\)，有：
\[
\sum_{i=1}^{n} a_i b_{n-i+1} \le \sum_{i=1}^{n} a_i b_{\pi(i)} \le \sum_{i=1}^{n} a_i b_i
\]
即：顺序和 >= 乱序和 >= 逆序和。
应用
- 最大化乘积之和：同序排列
- 最小化乘积之和：逆序排列
- 典型问题：贪心中的"代价最小化"问题
3.3 贪心算法原理¶
什么是贪心算法？¶
贪心算法是一种每一步都选择当前最优解的策略，期望通过局部最优达到全局最优。
graph LR
A["问题"] --> B["分解为若干子问题"]
B --> C["每步选当前最优"]
C --> D["得到全局解"]贪心的两个关键性质¶
1. 贪心选择性质¶
通过做出局部最优选择，能够导致全局最优解。即：存在一个最优解包含当前的贪心选择。
2. 最优子结构¶
问题的最优解包含其子问题的最优解。
贪心 vs 动态规划
| 特征 | 贪心 | 动态规划 |
|---|---|---|
| 决策方式 | 每步只看当前最优 | 考虑所有子问题 |
| 是否回退 | 不回退 | 会考虑多种方案 |
| 正确性 | 需要证明 | 有状态转移方程保证 |
| 效率 | 通常更快 | 可能较慢 |
贪心的一般步骤¶
- 证明贪心策略的正确性（反证法 / 调整法）
- 设计贪心策略
- 实现算法
如何证明贪心正确
假设存在一个最优解不采用贪心选择，通过"调整"（把非贪心选择替换为贪心选择），证明调整后的解不差于原最优解。
3.4 经典贪心模型¶
3.4.1 区间调度问题（活动选择）¶
问题描述：有 n 个活动，每个活动有开始时间和结束时间。一个人同时只能参加一个活动，求最多能参加多少个活动。
贪心策略：按照结束时间排序，每次选择结束最早且不与已选活动冲突的活动。
正确性证明
设贪心解选了活动 \(a_1, a_2, \dots, a_k\)，最优解选了 \(b_1, b_2, \dots, b_m\)（按结束时间排序）。 对于 \(a_i\) 和 \(b_i\)，由于 \(a_i\) 是结束最早的可选活动，所以 \(a_i\) 的结束时间 \(\le b_i\) 的结束时间。 这意味着 \(a_i\) 给后续活动留出了更多空间，因此贪心解不会比最优解差。
#include <bits/stdc++.h>
using namespace std;
struct Interval {
int start, end;
};
// 按结束时间排序
bool cmp(const Interval& a, const Interval& b) {
return a.end < b.end;
}
// 区间调度：返回最多能选多少个不重叠区间
int intervalScheduling(vector<Interval>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
int count = 0; // 已选活动数
int lastEnd = -1e9; // 上一个活动的结束时间
for (auto& it : intervals) {
// 如果当前活动开始时间 >= 上一个活动结束时间
if (it.start >= lastEnd) {
count++;
lastEnd = it.end;
}
}
return count;
}
int main() {
vector<Interval> intervals = {{1, 3}, {2, 5}, {4, 7}, {8, 10}};
cout << intervalScheduling(intervals) << endl; // 输出: 3
// 按结束时间排序后依次选 {1,3}, {4,7}, {8,10}
// {2,5} 因与 {1,3} 重叠而被跳过
return 0;
}
复杂度分析：排序 O(n log n) + 遍历 O(n) = O(n log n)
3.4.2 分配问题¶
分糖果问题¶
问题描述：有 n 个孩子和 m 个糖果，每个孩子有一个需求值，每个糖果有一个大小。一个糖果只能分给一个孩子，且糖果大小 >= 需求值才算满足。求最多能满足多少个孩子。
贪心策略：将孩子需求和糖果大小都排序，用最小的能满足的糖果分给当前需求最小的孩子。
#include <bits/stdc++.h>
using namespace std;
// 分糖果：求最多能满足多少个孩子
int distributeCandies(vector<int>& children, vector<int>& candies) {
sort(children.begin(), children.end());
sort(candies.begin(), candies.end());
int i = 0, j = 0; // i 指向孩子，j 指向糖果
int count = 0;
while (i < children.size() && j < candies.size()) {
if (candies[j] >= children[i]) {
// 当前糖果能满足当前孩子
count++;
i++;
j++;
} else {
// 当前糖果太小，尝试更大的糖果
j++;
}
}
return count;
}
int main() {
vector<int> children = {1, 2, 3}; // 孩子的需求
vector<int> candies = {1, 1, 3}; // 糖果的大小
cout << distributeCandies(children, candies) << endl; // 输出: 2
return 0;
}
任务分配问题¶
问题描述：有 n 个任务，每个任务有一个截止时间和一个利润。每个任务需要 1 个单位时间完成，求在截止时间内完成任务能得到的最大利润。
贪心策略：按利润降序排序，对于每个任务，尽量安排在截止时间之前的最晚空闲时间。
#include <bits/stdc++.h>
using namespace std;
struct Task {
int deadline, profit;
};
// 任务调度：求最大利润
int taskScheduling(vector<Task>& tasks) {
// 按利润降序排序
sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) {
return a.profit > b.profit;
});
// 找最大截止时间
int maxDeadline = 0;
for (auto& t : tasks) maxDeadline = max(maxDeadline, t.deadline);
// 记录每个时间槽是否已被占用
vector<bool> slot(maxDeadline + 1, false);
int totalProfit = 0;
for (auto& t : tasks) {
// 从截止时间往前找空闲时间槽
for (int d = t.deadline; d >= 1; d--) {
if (!slot[d]) {
slot[d] = true;
totalProfit += t.profit;
break;
}
}
}
return totalProfit;
}
3.4.3 跳跃游戏¶
问题描述：给定一个非负整数数组 nums，每个元素表示在该位置可以跳跃的最大长度。判断能否到达最后一个下标。
贪心策略：维护当前能到达的最远位置 maxReach，遍历过程中不断更新。
#include <bits/stdc++.h>
using namespace std;
// 跳跃游戏 I：判断能否到达终点
bool canJump(vector<int>& nums) {
int maxReach = 0; // 当前能到达的最远位置
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i > maxReach) return false; // 当前位置无法到达
maxReach = max(maxReach, i + nums[i]); // 更新最远距离
if (maxReach >= n - 1) return true; // 已能到达终点
}
return true;
}
// 跳跃游戏 II：求到达终点的最少跳跃次数
int jump(vector<int>& nums) {
int n = nums.size();
int jumps = 0; // 跳跃次数
int curEnd = 0; // 当前跳跃能到达的边界
int farthest = 0; // 当前范围内能到达的最远位置
for (int i = 0; i < n - 1; i++) {
farthest = max(farthest, i + nums[i]);
if (i == curEnd) { // 到达当前跳跃的边界
jumps++;
curEnd = farthest; // 更新边界
}
}
return jumps;
}
int main() {
vector<int> nums1 = {2, 3, 1, 1, 4};
cout << canJump(nums1) << endl; // 输出: 1 (true)
cout << jump(nums1) << endl; // 输出: 2
vector<int> nums2 = {3, 2, 1, 0, 4};
cout << canJump(nums2) << endl; // 输出: 0 (false)
return 0;
}
复杂度分析：O(n)，只需遍历一次。
3.4.4 会议室问题¶
问题描述：给定一系列会议的开始和结束时间，判断一个人能否参加所有会议（即无重叠）。
扩展：若有多个人，求最少需要多少间会议室。
#include <bits/stdc++.h>
using namespace std;
// 方法一：判断是否所有会议都不重叠（排序后检查相邻区间）
bool canAttendMeetings(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] < intervals[i - 1][1])
return false; // 有重叠
}
return true;
}
// 方法二：求最少需要多少间会议室（差分/优先队列）
int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
// 小顶堆：存储每间会议室的结束时间
priority_queue<int, vector<int>, greater<int>> pq;
for (auto& it : intervals) {
// 如果最早结束的会议室可以复用
if (!pq.empty() && pq.top() <= it[0]) {
pq.pop();
}
pq.push(it[1]); // 分配一间会议室
}
return pq.size(); // 堆的大小就是需要的会议室数量
}
int main() {
vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
cout << canAttendMeetings(intervals) << endl; // 输出: 0 (false)
cout << minMeetingRooms(intervals) << endl; // 输出: 2
return 0;
}
复杂度分析：排序 O(n log n) + 优先队列操作 O(n log n) = O(n log n)
拓展：反悔贪心
普通贪心一旦做出选择就不回头，而反悔贪心允许"先贪着选上，发现更优时用优先队列把之前最差的选择换掉"，从而在无法直接证明贪心正确的场景下仍能得到最优解。典型例题：洛谷 P2949 [USACO09OPEN] Work Scheduling G（按截止时间处理任务，用小顶堆维护已选任务的利润，堆顶利润低于当前任务时反悔替换），LeetCode 630 Course Schedule III 也是同款套路。
3.5 模拟题技巧¶
模拟题是竞赛中常见的一类题目，不涉及复杂算法，重点在于细心和代码组织能力。
常见模拟题类型¶
| 类型 | 示例 | 技巧 |
|---|---|---|
| 矩阵模拟 | 螺旋矩阵、旋转矩阵 | 定义方向数组，逐层处理 |
| 字符串模拟 | 大数运算、格式化输出 | 按位处理，注意进位/借位 |
| 游戏模拟 | 扫雷、生命游戏 | 使用副本数组避免状态干扰 |
| 流程模拟 | 机器指令执行 | 按题目描述逐步实现 |
方向数组技巧¶
// 方向数组：上下左右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 八个方向（含对角线）
int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// 遍历四个方向
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// (nx, ny) 是合法的相邻位置
}
}
模拟题通用策略¶
- 先读完题：确保完全理解题意，注意边界条件
- 分解步骤：将大问题拆成小步骤，逐步实现
- 使用副本：在涉及状态变化时（如生命游戏），使用副本数组
- 注意边界：数组越界、空串处理、特殊值等
- 写完自测：用小数据手动验证每一步
示例：螺旋矩阵
#include <bits/stdc++.h>
using namespace std;
// 螺旋矩阵：按螺旋顺序填充 1~n*n
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> mat(n, vector<int>(n, 0));
int dx[] = {0, 1, 0, -1}; // 右、下、左、上
int dy[] = {1, 0, -1, 0};
int x = 0, y = 0, dir = 0;
for (int val = 1; val <= n * n; val++) {
mat[x][y] = val;
// 计算下一个位置
int nx = x + dx[dir];
int ny = y + dy[dir];
// 如果越界或已填充，转向
if (nx < 0 || nx >= n || ny < 0 || ny >= n || mat[nx][ny] != 0) {
dir = (dir + 1) % 4;
nx = x + dx[dir];
ny = y + dy[dir];
}
x = nx;
y = ny;
}
return mat;
}
练习题¶
LeetCode 暑假 - 贪心专题¶
| 题号 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|
| 1323 | Maximum 69 Number | Easy | 链接 | - [ ] |
| 2027 | Minimum Moves to Convert String | Easy | 链接 | - [ ] |
| 680 | Valid Palindrome II | Easy | 链接 | - [ ] |
| 2259 | Remove Digit From Number to Maximize Result | Easy | 链接 | - [ ] |
| 1328 | Break a Palindrome | Medium | 链接 | - [ ] |
| 344 | Reverse String | Easy | 链接 | - [ ] |
| 402 | Remove K Digits | Medium | 链接 | - [ ] |
| 347 | Top K Frequent Elements | Medium | 链接 | - [ ] |
| 435 | Non-overlapping Intervals | Medium | 链接 | - [ ] |
| 1405 | Longest Happy String | Medium | 链接 | - [ ] |
| 93 | Restore IP Addresses | Medium | 链接 | - [ ] |
| 135 | Candy | Hard | 链接 | - [ ] |
| 2366 | Minimum Replacements to Sort the Array | Hard | 链接 | - [ ] |
| 1402 | Reducing Dishes | Hard | 链接 | - [ ] |
| 1659 | Maximize Grid Happiness | Hard | 链接 | - [ ] |
| 1330 | Reverse Subarray To Maximize Array Value | Hard | 链接 | - [ ] |
模拟题（扩展）¶
| 题号 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|
| 566 | Reshape the Matrix | Easy | 链接 | - [ ] |
| 415 | Add Strings | Easy | 链接 | - [ ] |
| 1252 | Cells with Odd Values in a Matrix | Easy | 链接 | - [ ] |
| 2717 | Semi-Ordered Permutation | Easy | 链接 | - [ ] |
| 20 | Valid Parentheses | Easy | 链接 | - [ ] |
| 289 | Game of Life | Medium | 链接 | - [ ] |
| 592 | Fraction Addition and Subtraction | Medium | 链接 | - [ ] |
| 1324 | Print Words Vertically | Medium | 链接 | - [ ] |
| 959 | Regions Cut By Slashes | Medium | 链接 | - [ ] |
| 22 | Generate Parentheses | Medium | 链接 | - [ ] |
| 68 | Text Justification | Hard | 链接 | - [ ] |
| 224 | Basic Calculator | Hard | 链接 | - [ ] |
| 2296 | Design a Text Editor | Hard | 链接 | - [ ] |
| 2056 | Number of Valid Move Combinations On Chessboard | Hard | 链接 | - [ ] |
| 749 | Contain Virus | Hard | 链接 | - [ ] |
ACM Day1 - 贪心部分¶
| 题号 | 平台 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|---|
| 1919C | CF | Grouping Increases | 1400 | 链接 | - [ ] |
| 1989C | CF | Two Movies | 1400 | 链接 | - [ ] |
| 1923C | CF | Find B | 1400 | 链接 | - [ ] |
| 2131E | CF | Adjacent XOR | 1400 | 链接 | - [ ] |
| abc342_d | AT | Square Pair | 1447 | 链接 | - [ ] |
| abc375_d | AT | ABBC | 1482 | 链接 | - [ ] |
| abc350_d | AT | New Friends | 1503 | 链接 | - [ ] |
| P9752 | 洛谷 | 密码锁 | 1600 | 链接 | - [ ] |
| P7913 | 洛谷 | 廊桥分配 | 1650 | 链接 | - [ ] |
| P7961 | 洛谷 | 数列 | 1700 | 链接 | - [ ] |
| P7084 | 洛谷 | 移球游戏 | 1800 | 链接 | - [ ] |
寒假排序相关¶
| 题号 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|
| 15 | 3Sum | Medium | 链接 | - [ ] |
| 169 | Majority Element | Easy | 链接 | - [ ] |
| 75 | Sort Colors | Medium | 链接 | - [ ] |
| 179 | Largest Number | Medium | 链接 | - [ ] |
本章小结¶
mindmap
root((排序与贪心))
排序算法
冒泡排序
选择排序
插入排序
归并排序
快速排序
堆排序
非比较排序
计数排序
桶排序
基数排序
排序应用
自定义比较函数
sort 高级用法
排序不等式
贪心算法
贪心选择性质
最优子结构
区间调度
分配问题
跳跃游戏
会议室问题
反悔贪心
模拟题
方向数组
矩阵模拟
字符串模拟名言
"贪心算法的难点不在于实现，而在于证明其正确性。" -- 在做贪心题时，一定要想清楚为什么当前的选择是正确的。