贪心

本页面将简要介绍贪心算法．

引入

贪心算法（greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程．这个人十分贪婪，每一步行动总是按某种指标选取最优的操作．而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响．

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性．

解释

适用范围

贪心算法在有最优子结构的问题中尤为有效．最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解．¹

证明

常见的证明思路包括交换论证和数学归纳法，两者也可以结合使用．

1. 交换论证：从任意一个最优解出发，通过有限次保持可行性且不使目标值变差的交换或替换，将其变为贪心算法得到的解，从而证明贪心解也是最优解．常用反证法书写证明．
2. 归纳法：先算得出边界情况（例如 $n=1$）的最优解 $F_1$，然后再证明：对于每个 $n$，$F_{n+1}$ 都可以由 $F_n$ 推导出结果．

要点

常见题型

在提高组难度以下的题目中，最常见的贪心有两种．

• 将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择．
• 每次取 XXX 中最大/小的东西，并更新 XXX．（有时取最大/小值的操作可以优化，比如用优先队列维护）

二者的区别在于前一种一定是离线的，可以先处理后选择；后一种可能是在线的，需要边处理边选择．

排序解法

用排序法/邻项交换法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值．

例题 NOIP 2012 国王游戏

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏．首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数．然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面．排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果．

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能少．注意，国王的位置始终在队伍的最前面．

解题思路

设当前排列中第 $i$ 个大臣左右手上的数分别为 $a_i,b_i$．考虑通过邻项交换法推导贪心策略．

先忽略向下取整，用 $s$ 表示第 $i$ 个大臣前面所有人的 $a_i$ 的乘积．交换前两人之中的最大奖赏为

$$\begin{array}{}\text{(}\text{1}\text{)}& \frac{s}{b_i{b}_{i+1}}max(b_{i+1},a_i{b}_i),\end{array}$$

交换后两人之中的最大奖赏为

$$\begin{array}{}\text{(}\text{2}\text{)}& \frac{s}{b_i{b}_{i+1}}max(b_i,a_{i+1}{b}_{i+1}).\end{array}$$

若 $a_i{b}_i\le a_{i+1}{b}_{i+1}$，由于 $b_{i+1}\le a_{i+1}{b}_{i+1}$，故 $(1)$ 式不大于 $(2)$ 式．向下取整是单调的，且 $max(\lfloor u\rfloor ,\lfloor v\rfloor )=\lfloor max(u,v)\rfloor$，所以两人交换顺序后最大奖赏不会变小．因此按 $a_i{b}_i$ 升序排序即为最优解．

实现的时候我们将输入的两个数用一个结构体来保存并重载运算符：

struct uv {
  int a, b;

  bool operator<(const uv& x) const { return 1LL * a * b < 1LL * x.a * x.b; }
};

后悔解法

思路是先临时接受新选项；若发生约束冲突，就在已选集合中撤销按贪心准则最差的选项．策略仍需正确性证明．

例题 「USACO09OPEN」工作调度 Work Scheduling

约翰的工作日从 $0$ 时刻开始，有 ${10}^9$ 个单位时间．在任一单位时间，他都可以选择编号 $1$ 到 $N$ 的 $N(1\le N\le {10}^5)$ 项工作中的任意一项工作来完成．工作 $i$ 的截止时间是 $D_i(1\le D_i\le {10}^9)$，完成后获利是 $P_i(1\le P_i\le {10}^9)$．在给定的工作利润和截止时间下，求约翰能够获得的利润最大为多少．

解题思路

1. 先假设每一项工作都做，将各项工作按截止时间排序后入队；
2. 在判断第 i 项工作做与不做时，若其截止时间符合条件，则将其与队中报酬最小的元素比较，若第 i 项工作报酬较高（后悔），则 ans += a[i].p - q.top()．
   用优先队列（小根堆）来维护队首元素最小．
3. 当 a[i].d<=q.size() 可以这么理解从 0 开始到 a[i].d 这个时间段只能做 a[i].d 个任务，而若 q.size()>=a[i].d 说明完成 q.size() 个任务时间大于等于 a[i].d 的时间，所以当第 i 个任务获利比较大的时候应该把最小的任务从优先级队列中换出．

参考代码

C++Python

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

struct f {
  long long d;
  long long p;
} a[100005];

bool cmp(f A, f B) { return A.d < B.d; }

// 小根堆维护最小值
priority_queue<long long, vector<long long>, greater<long long>> q;

int main() {
  long long n, i;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> a[i].d >> a[i].p;
  }
  sort(a + 1, a + n + 1, cmp);
  long long ans = 0;
  for (i = 1; i <= n; i++) {
    if (a[i].d <= (int)q.size()) {  // 超过截止时间
      if (q.top() < a[i].p) {       // 后悔
        ans += a[i].p - q.top();
        q.pop();
        q.push(a[i].p);
      }
    } else {  // 直接加入队列
      ans += a[i].p;
      q.push(a[i].p);
    }
  }
  cout << ans << endl;
  return 0;
}

from heapq import heappush, heapreplace

a = [tuple(map(int, input().split())) for _ in range(int(input()))]
a.sort(key=lambda job: job[0])  # 按截止时间升序排列

ans = 0  # 记录总收益
q = []  # 小根堆维护最小值
for d, p in a:
    if d <= len(q):  # 超过截止时间
        if q[0] < p:  # 后悔
            ans += p - heapreplace(q, p)
    else:  # 直接加入队列
        ans += p
        heappush(q, p)
print(ans)

复杂度分析

• 空间复杂度：当输入 $n$ 个任务时使用 $n$ 个 $a$ 数组元素，优先队列中最差情况下会储存 $n$ 个元素，则空间复杂度为 $O(n)$．
• 时间复杂度：std::sort 的时间复杂度为 $O(n\log n)$，维护优先队列的时间复杂度为 $O(n\log n)$，综上所述，时间复杂度为 $O(n\log n)$．

与动态规划的区别

常规贪心依赖可证明安全的局部选择；动态规划则维护各状态的最优值并比较候选转移．

习题

• 「USACO1.3」Barn Repair
• 洛谷 P2123 皇后游戏
• LeetCode 上标签为贪心算法的题目

参考资料与注释

---

1. 贪心算法 - 维基百科，自由的百科全书 ↩

---

本页面最近更新：2026/9/28 01:09:54，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, Ir1d, H-J-Granger, NachtgeistW, ksyx, countercurrent-time, Enter-tainer, mgt, Tiphereth-A, abc1763613206, HeRaNO, Makkiy, niltok, sshwy, AngelKitty, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Henry-ZHR, hsfzLZH1, Konano, LovelyBuggies, Marcythm, minghu6, ouuan, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, weiyong1024, c-forrest, Chrogeek, FTYC919, GavinZhengOI, Gesrua, Great-designer, iamtwz, kenlig, kxccc, LeiJinpeng, leoleoasd, lychees, Peanut-Tang, Planet6174, qiqistyle, RoxasKing, shawlleyw, SukkaW, tinjyu, Xeonacid, zirnc
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用