Day2 贪心、前缀和、差分学习笔记
2026-07-22 22:50:15
发布于：广东
XP02 Day2 贪心、前缀和、差分学习笔记
一、贪心算法
1. 贪心算法的专业概念
贪心算法是指：
在解决问题的每一步，都选择当前看起来最优的方案，
希望通过一连串局部最优选择，最终得到全局最优答案。
这句话里有两个关键词：
局部最优：当前这一步最好的选择。
全局最优：整个问题最后最好的答案。
用更通俗的话说：
每一步都选眼前最好的，希望最后整体也是最好的。
2. 生活中的贪心例子
假设你要买一本 37 元的书，手里有很多面值的钱：
20 元、10 元、5 元、1 元
如果想用尽量少的纸币张数付款，一种自然想法是：
能用大的就先用大的。
过程：
先用 20，还差 17
再用 10，还差 7
再用 5，还差 2
再用两个 1
最后用了：
20 + 10 + 5 + 1 + 1 = 37
这个过程就是一种贪心：
每一步都尽量选择当前能用的最大面值。
3. 贪心算法不是乱选
贪心不是随便选一个看起来舒服的答案。
它需要有一个明确规则，例如：
每次选最大的。
每次选最小的。
每次选结束最早的。
每次选花费最少的。
而且这个规则必须真的能得到正确答案。
所以使用贪心时，要想清楚：
我每一步贪什么？
为什么这样贪不会出错？
4. 样例解释：最多能买几支笔
题目：
小明有 m 元钱。
商店里有 n 支笔，每支笔价格不同。
每支笔最多买一支。
问小明最多能买几支笔？
输入：
n m
a1 a2 a3 ... an
其中 ai 表示第 i 支笔的价格。
样例：
5 10
6 2 4 3 8
意思是：
有 5 支笔，小明有 10 元。
每支笔价格分别是 6、2、4、3、8。
5. 贪心分析
想买尽量多的笔，就应该优先买便宜的笔。
为什么？
每买一支便宜的笔，花的钱更少，剩下的钱更多，就更有机会继续买下一支。
所以贪心规则是：
每次买当前最便宜的笔。
我们可以先把价格从小到大排序：
2 3 4 6 8
然后从便宜到贵买：
买 2，剩 8
买 3，剩 5
买 4，剩 1
买不起 6，停止
最多可以买：
3 支
6. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (m >= a[i]) {
m -= a[i];
cnt++;
} else {
break;
}
}
cout << cnt << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
7. 代码解释
排序：
sort(a + 1, a + n + 1);
把价格从小到大排好。
统计答案：
int cnt = 0;
表示已经买了多少支笔。
如果钱够：
if (m >= a[i])
就买这支笔：
m -= a[i];
cnt++;
如果钱不够：
break;
因为后面的笔更贵，也买不起了，可以直接停止。
8. 贪心题的思考步骤
做贪心题，可以按下面顺序想：
第一步：题目要最大化还是最小化什么？
第二步：每一步可以做什么选择？
第三步：当前这一步选什么最划算？
第四步：这个选择会不会影响后面？
第五步：写代码实现这个选择规则。
9. 贪心算法提醒
贪心很快，也经常很好写。
但要注意：
不是所有题都能贪心。
如果一个题目中：
当前选了最好的，后面可能变得很差。
那么贪心就可能错误。
初学阶段先记住：
贪心要有明确规则，不能凭感觉乱选。
10. 作业：T1、T2
T1、T2 是贪心算法练习题。
做题时请先写出：
本题贪心规则是什么？
为什么这样选？
排序吗？
每一步怎样更新答案？
建议解题格式：
1. 题目目标：
2. 贪心规则：
3. 需要排序的内容：
4. 变量含义：
5. 输出答案：
二、前缀和
1. 问题引入：蚂蚁吃米
有一只蚂蚁连续吃了 n 天米。
第 i 天吃了 ai 粒米。
现在有 q 次询问，每次问：
第 l 天到第 r 天一共吃了多少粒米？
例如：
n = 5
a = 2 4 1 3 6
如果问：
l = 2, r = 4
答案是：
a[2] + a[3] + a[4] = 4 + 1 + 3 = 8
2. 暴力解法
最直接的方法是：
每次询问，都从 l 加到 r。
代码大概是：
int sum = 0;
for (int i = l; i <= r; i++) {
sum += a[i];
}
cout << sum << endl;
这个方法容易理解。
但如果：
n 很大，q 也很大
每次都重新加一遍，就会很慢。
3. 暴力解法的时间复杂度
一次询问，最坏可能要加 n 个数。
如果有 q 次询问，那么最坏大约是：
O(n * q)
例如：
n = 100000
q = 100000
那么大约要做：
100000 * 100000 = 10000000000
也就是 10^10 次。
这通常会超时。
所以我们要想办法优化。
4. 前缀和能解决什么问题？
前缀和主要解决：
静态数组的区间和查询问题。
也就是：
数组不会一直修改；
但是会多次询问某一段的和。
例如：
第 l 天到第 r 天一共吃了多少米？
第 l 个数到第 r 个数的总和是多少？
某段成绩总分是多少？
某段路程总长度是多少？
5. 前缀和的算法思想
前缀和就是提前算好：
从第 1 个数加到第 i 个数的和。
我们用 s[i] 表示：
s[i] = a[1] + a[2] + ... + a[i]
例如：
a: 2 4 1 3 6
那么：
s[1] = 2
s[2] = 2 + 4 = 6
s[3] = 2 + 4 + 1 = 7
s[4] = 2 + 4 + 1 + 3 = 10
s[5] = 2 + 4 + 1 + 3 + 6 = 16
表格：
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
a[i] |
2 | 4 | 1 | 3 | 6 |
s[i] |
2 | 6 | 7 | 10 | 16 |
6. 前缀和的算法过程
先定义：
s[0] = 0
然后从 1 到 n 计算：
s[i] = s[i - 1] + a[i]
这句话的意思是：
前 i 个数的和 = 前 i - 1 个数的和 + 第 i 个数
如果要求 [l, r] 的和：
a[l] + a[l + 1] + ... + a[r]
可以用：
s[r] - s[l - 1]
为什么？
因为：
s[r] = a[1] + a[2] + ... + a[l - 1] + a[l] + ... + a[r]
s[l - 1] = a[1] + a[2] + ... + a[l - 1]
两者相减，前面多余的部分就去掉了。
剩下：
a[l] + ... + a[r]
7. 前缀和代码实现：数组准备
为了让公式更好写，本节课使用从 1 开始的下标。
定义数组：
const int N = 1e5 + 10;
long long a[N], s[N];
为什么用 long long？
因为很多数加起来可能超过 int 范围。
例如：
100000 个数，每个都是 100000
总和是 10000000000
这个数比 int 能存的范围大，所以用 long long 更安全。
8. 前缀和代码实现：读入数据
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
这里：
n 表示天数或数组长度
q 表示询问次数
a[i] 表示第 i 个数
9. 前缀和代码实现：计算 s 数组
s[0] = 0;
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
这段代码是前缀和最核心的部分。
每次计算：
当前前缀和 = 上一个前缀和 + 当前数字
例如：
s[3] = s[2] + a[3]
表示：
前 3 个数的和 = 前 2 个数的和 + 第 3 个数
10. 前缀和代码实现：回答询问
每次输入 l 和 r：
int l, r;
cin >> l >> r;
区间 [l, r] 的和是：
s[r] - s[l - 1]
所以：
cout << s[r] - s[l - 1] << endl;
11. 前缀和完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long a[N], s[N];
void solve() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
s[0] = 0;
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
while (q--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
12. 前缀和复杂度
计算前缀和数组：
O(n)
每次询问：
O(1)
如果有 q 次询问，总复杂度：
O(n + q)
比暴力的：
O(n * q)
快很多。
13. 前缀和易错点
易错点一：忘记 s[0] = 0
s[0] = 0;
当 l = 1 时，要用：
s[r] - s[0]
所以 s[0] 很重要。
易错点二：公式写错
正确公式：
s[r] - s[l - 1]
不是：
s[r] - s[l]
易错点三：没用 long long
如果数据较大，总和可能超过 int，建议使用：
long long
14. 算法应用：T3、T4
T3、T4 是前缀和应用题。
看到题目中有这些关键词时，要想到前缀和：
多次询问
区间和
第 l 个到第 r 个
一段时间内的总数
做题时先写出：
s[i] 表示什么？
区间 [l, r] 的答案怎么用 s 表示？
三、差分
1. 问题引入：区间加
现在有一个数组：
a[1], a[2], ..., a[n]
有 m 次操作，每次操作给出：
l r x
表示：
把 a[l] 到 a[r] 每个数都加上 x。
最后输出整个数组。
例如：
a: 1 2 3 4 5
操作：2 4 10
表示第 2 到第 4 个数都加 10。
结果：
1 12 13 14 5
2. 暴力解法
最直接的方法：
for (int i = l; i <= r; i++) {
a[i] += x;
}
一次操作最坏要改 n 个数。
如果有 m 次操作，最坏复杂度是：
O(n * m)
如果：
n = 100000
m = 100000
大约要做：
10^10
次操作，通常会超时。
所以需要优化。
3. 差分能解决什么问题？
差分主要解决：
数组的多次区间修改问题。
特别是这种操作：
把 [l, r] 这一段全部加上 x。
如果题目最后才问整个数组结果，差分非常适合。
4. 差分和前缀和的关系
差分是依托前缀和的。
可以这样理解：
前缀和：由原数组得到累计和。
差分：记录相邻两个数之间的变化。
如果有原数组：
a: 1 3 6 10
差分数组 b 可以这样定义：
b[1] = a[1]
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]
b[4] = a[4] - a[3]
得到：
b: 1 2 3 4
如果我们对 b 求前缀和：
b[1] = 1
b[1] + b[2] = 3
b[1] + b[2] + b[3] = 6
b[1] + b[2] + b[3] + b[4] = 10
又能得到原数组：
a: 1 3 6 10
所以：
差分数组通过前缀和可以还原成原数组。
5. 差分的算法思想
如果要让 [l, r] 这一段都加上 x，差分数组只需要改两个位置：
b[l] += x;
b[r + 1] -= x;
为什么这样可以？
从 l 开始：
后面的数都会因为 b[l] += x 而多 x。
到 r + 1：
再用 b[r + 1] -= x 把这个影响取消。
所以真正受到影响的是：
l 到 r
6. 用例子理解差分
原数组：
a: 1 2 3 4 5
先建立差分：
b[1] = 1
b[2] = 2 - 1 = 1
b[3] = 3 - 2 = 1
b[4] = 4 - 3 = 1
b[5] = 5 - 4 = 1
所以：
b: 1 1 1 1 1
现在执行操作：
2 4 10
也就是 [2, 4] 每个数加 10。
差分中操作：
b[2] += 10
b[5] -= 10
新的差分：
b: 1 11 1 1 -9
对 b 求前缀和还原：
a[1] = 1
a[2] = 1 + 11 = 12
a[3] = 12 + 1 = 13
a[4] = 13 + 1 = 14
a[5] = 14 + (-9) = 5
结果：
1 12 13 14 5
正好是我们想要的。
7. 差分的算法过程
差分题一般分四步：
第一步：读入原数组 a。
第二步：建立差分数组 b。
第三步：每次区间加，只修改 b[l] 和 b[r + 1]。
第四步：对 b 求前缀和，还原最终数组。
8. 差分代码实现：定义数组
const int N = 1e5 + 10;
long long a[N], b[N];
这里也建议使用 long long。
因为多次区间加之后，数字可能变得很大。
9. 差分代码实现：读入原数组
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
其中：
n 表示数组长度
m 表示操作次数
10. 差分代码实现：建立差分数组
根据定义：
b[i] = a[i] - a[i - 1]
代码：
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i - 1];
}
这里默认：
a[0] = 0
所以：
b[1] = a[1] - a[0] = a[1]
11. 差分代码实现：处理区间加
每次操作输入：
int l, r;
long long x;
cin >> l >> r >> x;
执行：
b[l] += x;
b[r + 1] -= x;
注意：
r + 1 可能等于 n + 1。
所以数组要开大一点：
const int N = 1e5 + 10;
12. 差分代码实现：还原最终数组
处理完所有操作后，对 b 求前缀和：
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + b[i];
}
这一步表示：
用差分数组 b 还原最终的 a 数组。
然后输出：
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
13. 差分完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long a[N], b[N];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i - 1];
}
while (m--) {
int l, r;
long long x;
cin >> l >> r >> x;
b[l] += x;
b[r + 1] -= x;
}
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + b[i];
}
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
14. 差分复杂度
建立差分数组：
O(n)
每次区间加：
O(1)
还原数组：
O(n)
如果有 m 次操作，总复杂度：
O(n + m)
比暴力的：
O(n * m)
快很多。
15. 差分易错点
易错点一：忘记修改 r + 1
正确写法：
b[l] += x;
b[r + 1] -= x;
易错点二：数组没有开大
因为会访问：
b[r + 1]
如果 r = n，就会访问：
b[n + 1]
所以数组要多开一点。
易错点三：还原数组时公式写错
正确写法：
a[i] = a[i - 1] + b[i];
也可以直接累加输出：
long long now = 0;
for (int i = 1; i <= n; i++) {
now += b[i];
cout << now << " ";
}
易错点四：把前缀和和差分混在一起
记住：
前缀和：快速求区间和。
差分：快速做区间加。
16. 算法应用：T5、T6
T5、T6 是差分应用题。
看到题目中有这些关键词时，要想到差分：
多次修改
区间加
把 l 到 r 都增加 x
最后输出整个数组
做题时先写出：
b[i] 表示什么？
每次操作要改 b 的哪两个位置？
最后怎样还原数组？
四、本节课总结
1. 贪心
贪心算法是：
每一步都选择当前最优，希望最终得到整体最优。
做贪心题要先确定：
贪心规则。
2. 前缀和
前缀和解决：
多次区间和查询。
核心公式：
s[i] = s[i - 1] + a[i];
区间 [l, r] 的和：
s[r] - s[l - 1]
3. 差分
差分解决：
多次区间加修改。
区间 [l, r] 全部加 x：
b[l] += x;
b[r + 1] -= x;
最后通过前缀和还原数组。
4. 前缀和与差分的区别
| 算法 | 主要解决 | 核心操作 |
|---|---|---|
| 前缀和 | 区间和查询 | s[r] - s[l - 1] |
| 差分 | 区间加修改 | b[l] += x; b[r + 1] -= x; |
课后练习
T1：贪心练习
完成题单中的 T1。
做题时写清楚：
贪心规则是什么？
为什么这样选？
T2：贪心练习
完成题单中的 T2。
如果题目需要排序，请想清楚：
按照什么排序？
从小到大还是从大到小？
T3：前缀和应用
完成题单中的 T3。
看到区间和询问时，先写：
s[i] = s[i - 1] + a[i];
然后用：
s[r] - s[l - 1]
回答询问。
T4：前缀和应用
完成题单中的 T4。
注意检查：
下标从 0 开始还是从 1 开始？
答案是否需要 long long？
T5：差分应用
完成题单中的 T5。
遇到区间加时，先想到：
b[l] += x;
b[r + 1] -= x;
T6：差分应用
完成题单中的 T6。
注意最后要通过前缀和还原：
a[i] = a[i - 1] + b[i];
本节课最重要的五句话
- 贪心是每一步选择当前最优，但必须有正确的贪心规则。
- 前缀和用于快速求区间和。
- 前缀和公式是
s[i] = s[i - 1] + a[i]。 - 差分用于快速进行区间加。
- 差分修改公式是
b[l] += x; b[r + 1] -= x;。
这里空空如也
有帮助，赞一个