Greedy Algorithms 贪心算法

什么是贪心算法？

贪心算法是一种在每一步选择中都采取局部最优解的算法，期望通过一系列局部最优选择达到全局最优。

贪心算法的特点

1. 贪心选择性质：每一步都做出当前最优的选择
2. 最优子结构：问题的最优解包含子问题的最优解
3. 不可回溯：一旦做出选择，就不再考虑其他可能

贪心 vs 动态规划

特征	贪心算法	动态规划
选择策略	只考虑当前最优	考虑所有可能
时间复杂度	通常 O(n) 或 O(nlogn)	通常 O(n²) 或更高
最优性	不保证全局最优	保证全局最优
适用问题	具有贪心选择性质	最优子结构

何时使用贪心？

贪心算法适用于满足以下条件的问题：

• 具有贪心选择性质
• 最优子结构
• 问题规模较大，需要高效算法

---

经典例题：Mad Scientist (USACO Bronze)

题目描述

给定两个长度为 n 的字符串 a 和 b，每次操作可以将 a 的任意连续子串反转。求最少需要多少次操作才能将 a 变成 b。

算法思路

核心思想：匹配段计数

使用 flag 标志当前是否处于”不匹配段”中：

• 当 flag=True（不在段中）时：
  • 若 a[i] != b[i]，说明开始一个新的不匹配段，ans++，flag 设为 False
• 当 flag=False（正在段中）时：
  • 若 a[i] == b[i]，说明当前不匹配段结束，flag 设回 True

最终 ans 即为答案。

正确性证明

每次操作（反转连续子串）可以消除一个连续的不匹配段。因此最少操作数等于不匹配段的个数。

贪心策略在遇到不匹配时立即开始新段，在匹配时立即结束当前段，能准确计数所有不匹配段。

代码实现

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)

---

经典例题：Watching Mooloo (USACO Bronze)

题目描述

https://usaco.org/index.php?page=viewproblem2&cpid=1301

农民 John 要观看 N 个电影，每个电影在第 $d_i$ 天上映（$1 \leq d_i \leq 10^{14}$，$d_1 < d_2 < \dots < d_N$）。

Mooloo 订阅规则：

• 订阅连续 $d$ 天的费用为 $d + K$ 美元（$1 \leq K \leq 10^9$）
• 可以随时开始订阅，也可以多次订阅

求农民 John 观看所有 N 部电影所需的最小总费用。

算法思路

贪心策略：尽可能将多个观影日期合并到同一个订阅中。

核心思想：

• 如果相邻两部电影的间隔为 $gap$，那么：
  • 合并订阅费用 = $gap + K$（从第 $d_1$ 天开始订阅 $gap$ 天）
  • 分开订阅费用 = $2 \times (K + 1)$（两个独立订阅各需 $K+1$ 天）
• 当 $gap + K > 2(K + 1)$，即 $gap > K + 1$ 时，分开订阅更划算
• 因此，当 $gap > K + 1$ 时开新订阅，否则合并到当前订阅

具体实现：

• 从第一天开始订阅
• 遍历后续观影日期，计算与上一个日期的间隔
• 如果间隔 $> K + 1$，则开始新订阅
• 否则继续使用当前订阅

正确性证明

贪心选择性质：对于任意相邻观影日期，如果间隔 $gap \leq K + 1$，合并订阅更优（$gap + K \leq 2(K + 1)$）；如果间隔 $gap > K + 1$，分开订阅更优。

最优子结构：假设已经确定前 $i$ 部电影的最佳订阅方案，那么对于第 $i+1$ 部电影：

• 如果 $d_{i+1} - d_i \leq K + 1$，将其加入当前订阅不会增加费用
• 如果 $d_{i+1} - d_i > 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)

核心要点

1. 每个订阅必须从观影日期开始，订阅 $K+1$ 天的费用为 $K+1+K=2K+1$
2. 贪心决策点：当 $gap > K + 1$ 时开新订阅，否则合并到当前订阅
3. 第一部电影也需要新订阅，费用为 $K + 1$

---

经典例题：Cow Tipping (USACO Bronze)

题目描述

https://usaco.org/index.php?page=viewproblem2&cpid=1060

给定一个 $N \times N$ 的格子（$N \leq 10$），每个格子上有一头牛：

• 0 = 站立（正确状态）
• 1 = 躺下（错误状态）

每次操作可以选择左上角为 (0, 0)、右下角为 (r, c) 的矩形，将该矩形内所有格子翻转（0 变 1，1 变 0）。

求最少需要多少次操作才能让所有格子变成 0。

算法思路

贪心策略：从右下角开始，逐个处理每个格子。

核心思想：

• 对于格子 (i, j)，如果它是 1（躺下），我们必须对以 (i, j) 为右下角的矩形进行操作才能改变它
• 这是因为操作只能影响左上角的矩形，且一旦处理完某个格子，后续操作不会影响到它

具体实现：

• 从右下角 (N-1, N-1) 开始
• 对于每个格子 (i, j)：
  • 如果当前值为 1，应用操作翻转以 (i, j) 为右下角的矩形
  • 计数器 +1
• 移动到下一个格子（先向左，到头后向上）

正确性证明

贪心选择性质：对于任意格子 (i, j)，如果它是 1，唯一能改变它的方式是对以 (i, j) 为右下角的矩形进行操作。更大的矩形会多余地翻转更多格子，因此最小的必要操作就是翻转以 (i, j) 为右下角的矩形。

最优子结构：假设我们已经处理完所有右下角在 (i, j) 之后的格子，现在处理格子 (i, j)：

• 如果它是 0，不需要操作，后续操作也不会影响它
• 如果它是 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² 个格子，总共最多 N² 次操作
• 空间复杂度：O(N²) - 存储网格

核心要点

1. 贪心策略：从右下角开始，每个格子只处理一次
2. 关键洞察：对于每个 1，唯一能消除它的方式是操作包含它的最小矩形
3. 为什么贪心有效：操作只影响左上方向的格子，从右下开始确保不会影响已处理的格子