贪心算法
贪心算法
策略速查
贪心在每一步选择当前最优的选项，通常与排序配合使用（先排序，再贪心）。核心是价值函数——决定哪个选择是最优的：
- 要最大化某个值 → 每次选择最大的
- 要最小化某个值 → 每次选择最小的
| 问题类型 | 贪心策略 |
|---|---|
| 最多选 k 个（耗时/体积受限） | 按耗时/体积升序选 |
| 活动安排 / 区间选点 | 按结束时间排序，选最早结束的 |
| 最少段覆盖不匹配 | 逐位扫描，段计数 |
| 间隔合并 vs 分开 | 比较合并代价与新建代价（如 $gap$ vs $K+1$） |
| 只能左移的重排 | 从左到右匹配，数需要移动的元素 |
| 硬币找零 | 仅特定面额系统有效 |
| 背包（价值/重量） | 无通用贪心，需 DP |
解释
贪心算法的特点
- 贪心选择性质：每一步都做出当前最优的选择
- 最优子结构：问题的最优解包含子问题的最优解
- 不可回溯：一旦做出选择，就不再考虑其他可能
正确性通常通过交换参数证法（exchange argument）证明：假设最优解中选了 B 而不是更优的 A，把 B 换成 A 不会变差，矛盾。
贪心 vs 动态规划
| 特征 | 贪心算法 | 动态规划 |
|---|---|---|
| 选择策略 | 只考虑当前最优 | 考虑所有可能 |
| 时间复杂度 | 通常 O(n) 或 O(nlogn) | 通常 O(n²) 或更高 |
| 最优性 | 不保证全局最优 | 保证全局最优 |
| 适用问题 | 具有贪心选择性质 | 最优子结构 |
何时使用贪心：具有贪心选择性质 + 最优子结构 + 问题规模较大需要高效算法。
贪心失效的例子
硬币找零：面额 {1, 3, 4}、目标 6——贪心解 4+1+1 用 3 枚，最优解 3+3 只要 2 枚。贪心只在特定面额系统（如美元、欧元）下有效。
背包问题：
| 物品 | 重量 | 价值 | 价值/重量 |
|---|---|---|---|
| A | 3 | 18 | 6 |
| B | 2 | 10 | 5 |
| C | 2 | 10 | 5 |
容量 4：贪心按价值/重量选 A（18），最优是 B+C（20）。背包需要动态规划解决。
例题
例题 1：学习算法（排序贪心入门）
来源：Codeforces - Very Easy
Steph 有 X 分钟时间学习算法，有 N 个算法，第 i 个需要 a_i 分钟。求最多能学多少个算法。（1 ≤ X ≤ 10^4，1 ≤ N ≤ 100）
思路：先学用时最短的——a_i 升序排列后依次累加，直到时间用完。
正确性（交换论证）：若最优解先选了用时更长的 B，把它换成用时更短的 A，总时间不增、可选数量不减，故先选最短总是最优。
algorithms.sort()
count = 0 # 已用时间
i = 0
while i < N and count + algorithms[i] <= X:
count += algorithms[i]
i += 1
print(i)复杂度：O(N log N)
例题 2：活动安排 Movie Festival（按结束时间排序）
来源：CSES - Easy
有 N 个活动，每个活动有开始和结束时间，每次只能全程参加一个。求最多能参加多少个活动。
错误策略：选最早开始的。反例：[(0,6), (5,10), (6,7)]——按最早开始只能选 1 个，最优是 [(0,6), (6,7)] 两个。
正确策略：选最早结束的，为后续留出更多时间。
正确性：设 E1 比 E2 结束早。能接在 E2 之后的活动 X 必然也能接在 E1 之后，所以选 E1 不会更差、后续可选集合更大。
events.sort(key=lambda x: x[1]) # 按结束时间排序
current_end = -1
ans = 0
for start, end in events:
if start >= current_end: # 可以参加
current_end = end
ans += 1
print(ans)复杂度：O(N log N)
例题 3：Mad Scientist（不匹配段计数）
来源：USACO Bronze - Mad Scientist（文件名 breedflip）
给定两个长度为 n 的字符串 a 和 b，每次操作可以将 a 的任意连续子串反转。求最少多少次操作将 a 变成 b。
思路：每次反转恰好消除一个连续的不匹配段，所以答案 = 不匹配段的个数。用 flag 扫描：不在段中遇到 a[i] != b[i] 就开新段计数，段中遇到相等就结束段。
import sys
sys.stdin = open("breedflip.in", "r")
sys.stdout = open("breedflip.out", "w")
n = int(input())
a = input()
b = input()
flag = True # True 表示当前不在不匹配段中
ans = 0
for i in range(n):
if flag:
if a[i] != b[i]: # 开始新的不匹配段
ans += 1
flag = False
else:
if a[i] == b[i]: # 不匹配段结束
flag = True
print(ans)复杂度：时间 O(n)，空间 O(1)
例题 4：Watching Mooloo（间隔合并 or 分开）
来源：USACO Bronze - Watching Mooloo
农民 John 要观看 N 个电影，第 $d_i$ 天上映（$1 \leq d_i \leq 10^{14}$，递增）。订阅连续 $d$ 天费用为 $d + K$ 美元（$1 \leq K \leq 10^9$），可多次订阅。求看完全部电影的最小总费用。
思路：比较相邻两部电影的间隔 $gap$——合并进当前订阅花费 $gap$，新开订阅花费 $K+1$（订 1 天付 $1+K$）。当 $gap > K + 1$ 时分开更划算，否则合并。
正确性（交换论证）：$gap \le K+1$ 时合并费用 $gap+K \le 2(K+1)$ 不劣于两次独立订阅；$gap > K+1$ 时分开严格更优。每个间隔的决策互不影响，局部最优叠加即全局最优。
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]
ans = k + 1
for i in range(1, n):
if arr[i] - arr[i - 1] <= k + 1:
ans += arr[i] - arr[i-1]
else:
ans += k + 1
print(ans)复杂度：时间 O(n)，空间 O(1)
关键点：每个订阅必须从某个观影日期开始；第一部电影也需要新订阅（费用 $K+1$）。
例题 5：Cow Tipping（从右下角逆序处理）
$N \times N$ 格子（$N \leq 10$），1 表示躺下。每次操作翻转左上角 (0,0)、右下角 (r,c) 的矩形。求最少操作次数使全变 0。
思路：从右下角 (N-1, N-1) 开始逐格处理——若当前格是 1，必须操作以它为右下角的矩形（这是唯一能改变它且不影响已处理格子的方式），计数 +1。
正确性：操作只影响左上方向，从右下开始保证已处理的格子不被破坏；每个 1 至少需要一次包含它的操作，贪心恰好达到该下界。
TIPPED = "0"
def flip(r: int, c: int, cows):
if cows[r][c]:
for ri in range(r + 1):
for ci in range(c + 1):
cows[ri][ci] = not cows[ri][ci]
return True
return False
with open("cowtip.in") as read:
width = int(read.readline())
cows = []
for _ in range(width):
row = read.readline()
to_add = []
for c in range(width):
to_add.append(row[c] != TIPPED)
cows.append(to_add)
min_flips = 0
x = width - 1
y = width - 1
while x >= 0 and y >= 0:
min_flips += flip(x, y, cows)
if x > 0:
x -= 1
else:
y -= 1
x = y
print(min_flips, file=open("cowtip.out", "w"))复杂度：时间 O(N³)（最多 $N^2$ 次操作、每次影响 $O(N^2)$ 格），空间 O(N²)
例题 6：Photo Shoot 2（只能左移的重排）
来源：USACO Bronze - Photo Shoot 2
给定两个长度为 N 的排列 a 和 b。每次操作可将一头牛向左移动任意多位置（不能向右）。求最少操作次数把 a 变成 b。
思路：双指针从左到右匹配目标排列——j 扫过当前排列中未被移动的牛；若第一个未移动的牛恰好是目标牛则指针后移，否则这头目标牛必须从后面移动过来，计数 +1 并标记 moved。
正确性：只能左移，所以从前向后匹配是唯一策略；每头需要移动的牛至少操作一次，贪心恰好达到该下界。
n = int(input())
arr = [int(x) for x in input().split()]
target = [int(x) for x in input().split()]
moved = [False] * (n + 1)
ans = 0
j = 0
for i in range(n):
while j < n and moved[arr[j]]:
j += 1
if j >= n:
break
if target[i] == arr[j]:
j += 1
else:
ans += 1
moved[target[i]] = True
print(ans)复杂度：时间 O(n)，空间 O(n)
关键点：moved 数组避免重复计已移动的牛；指针 j 单调右移保证整体线性。
总结
- 适用条件：最优子结构 + 贪心选择性质
- 先排序，再贪心；按结束时间排序是活动安排类问题的万能起点
- 用交换参数证法证明正确性
- 遇到硬币找零、背包等经典反例场景，果断换 DP