04_Greedy Algorithms 贪心算法

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 ≤ d_i ≤ 10¹⁴，d₁ < d₂ < … < d_N）。

Mooloo 订阅规则： - 订阅连续 d 天的费用为 d + K 美元（1 ≤ K ≤ 10⁹） - 可以随时开始订阅，也可以多次订阅

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

算法思路

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

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

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

正确性证明

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

最优子结构：假设已经确定前 i 部电影的最佳订阅方案，那么对于第 i + 1 部电影： - 如果 d_i + 1 − d_i ≤ 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 × N 的格子（N ≤ 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. 为什么贪心有效：操作只影响左上方向的格子，从右下开始确保不会影响已处理的格子