第八章：贪心与简单构造

算法

有些问题要求从许多方案中找到最优解，有些问题只要求给出任意一个满足限制的方案。贪心用于前一类问题：每一步固定一个当前选择，并证明至少存在一个最优解包含这个选择。构造用于后一类问题：根据限制直接生成答案，再逐项验证答案始终合法。

本章先通过区间调度完整经历一次“发现规则、寻找反例、证明规则、实现算法”的过程，再把交换论证用于排队问题，并介绍从左向右固定前缀的另一类贪心。最后单独讨论构造，避免把“最优性证明”和“合法性验证”混在一起。

阅读前需要掌握数组、排序、结构体和时间复杂度。

1. 从区间调度认识贪心

1.1 先确定当前选择解决了什么

例题：线段覆盖。

题意概述：给定 nn 个活动，第 ii 个活动占用半开区间 [ai,bi)[a_i,b_i)。同一时刻只能参加一个活动，求最多能够完整参加多少个活动。

数据范围为 1≤n≤1061\le n\le 10^6，0≤ai<bi≤1060\le a_i<b_i\le 10^6。

枚举所有活动子集，再检查其中的区间是否互不重叠，需要处理指数级数量的候选。为了减少候选，可以先考虑答案中的第一个活动。

第一个活动结束得越早，后面可使用的时间范围越大。因此可以尝试下面的规则：

  1. 按结束时间从早到晚排列所有活动；
  2. 选择当前能够参加且结束最早的活动；
  3. 删除与它冲突的活动，对剩余活动重复同样的过程。

例如有以下活动：

活动占用区间
AA[1,4)[1,4)
BB[3,5)[3,5)
CC[0,6)[0,6)
DD[5,7)[5,7)
EE[5,9)[5,9)
FF[8,9)[8,9)

按结束时间扫描时，先选择 AA。BB 和 CC 与 AA 冲突，不能再选；DD 的开始时间不早于 AA 的结束时间，可以选择；随后 FF 可以接在 DD 后面。最终得到 A,D,FA,D,F，共 33 个活动。

这个过程只说明了算法怎样运行，还没有说明它一定得到最优答案。贪心规则必须经过证明，不能只依据“留下的时间看起来更多”。

1.2 用交换论证固定第一个活动

设 gg 是所有活动中结束最早的一个。任取一个最优方案，设其中第一个活动为 oo。

因为 gg 的结束时间最早，所以

g.r≤o.r.g.r\le o.r.

把最优方案中的 oo 换成 gg。原来排在 oo 后面的活动都在 o.ro.r 时刻之后开始，也就一定不早于 g.rg.r 开始。因此替换后仍然没有区间冲突，活动数量也没有减少。

这说明：即使原来的最优方案没有选择 gg，也能把它改造成一个选择 gg 的最优方案。于是可以放心固定 gg，只处理在 gg 结束后开始的活动。

固定第一个活动后，剩余任务仍然是“从一组活动中选择最多的互不重叠区间”，问题结构没有改变。相同论证可以不断重复，直到没有活动可选。

证明得到的结论不是“所有最优方案都以 gg 开头”，而是“至少存在一个最优方案以 gg 开头”。这已经足以支持贪心选择。

1.3 把选择规则写成排序与扫描

排序后，每次遇到能接在已选活动之后的区间就选择它。以下结构体保存活动的左右端点，比较函数按右端点升序排列；右端点相同时，左右端点的先后不会影响最多活动数，这里再按左端点升序保证顺序确定。

struct Activity
{
    int l, r;
};

bool cmp(const Activity &x, const Activity &y)
{
    if (x.r != y.r)
    {
        return x.r < y.r;
    }
    return x.l < y.l;
}

sort(a + 1, a + n + 1, cmp);

int ans = 0, last = 0;
bool has = false;
for (int i = 1; i <= n; ++i)
{
    // 半开区间允许下一个活动恰好从 last 开始
    if (!has || a[i].l >= last)
    {
        ++ans;
        last = a[i].r;
        has = true;
    }
}

变量 lastlast 表示最后一个已选活动的结束时间，hashas 表示当前是否已经选择过活动。单独记录 hashas，可以避免人为设置一个“足够小”的初始结束时间。

这里使用半开区间 [ai,bi)[a_i,b_i)，所以一个活动在时刻 tt 结束，另一个活动可以恰好在时刻 tt 开始，判断条件为 ai≥lasta_i\ge last。若题目规定端点相接也算冲突，判断条件应改为严格大于。

排序需要 O(nlog⁡n)O(n\log n) 时间，扫描需要 O(n)O(n) 时间，因此总时间复杂度为 O(nlog⁡n)O(n\log n)；保存全部活动需要 O(n)O(n) 空间。

1.4 用反例排除错误规则

“按开始时间最早选择”不正确。例如活动为 [1,10)[1,10)、[2,3)[2,3)、[3,4)[3,4) 时，选择开始最早的 [1,10)[1,10) 只能参加 11 个活动，而后两个短活动可以连续参加。

“按区间长度最短选择”也不正确。例如活动为 [0,3)[0,3)、[2,4)[2,4)、[3,6)[3,6) 时，中间区间长度最短，却同时与另外两个区间冲突；选择两侧区间可以参加 22 个活动。

反例还能帮助确定结论的适用范围。本节目标是最大化活动数量；如果每个活动还有不同收益，结束最早的活动未必属于最优方案，必须重新分析选择规则。

2. 从案例中提炼贪心证明

2.1 局部规则只是候选策略

贪心算法通常具有以下过程：当前做出一个选择，不再撤销，然后继续处理剩余问题。真正需要证明的是，这个不可撤销的选择不会排除所有最优方案。

“每次选最大”“每次选最小”都只是一条候选规则。例如，用面值 1,3,41,3,4 的硬币凑出金额 66 时，每次选择不超过剩余金额的最大面值，会得到 4+1+14+1+1，共使用 33 枚硬币；最优方案是 3+33+3，只使用 22 枚。局部数值最大不等于整体答案最优。

设计规则后，可以先检查以下小数据：

  • 只有一个或两个对象；
  • 多个关键字相等；
  • 两种候选规则给出不同选择；
  • 局部最优选择会占用稀缺资源；
  • 题目限制恰好取到边界值。

小规模搜索也可以把贪心答案与暴力最优答案对比，用于发现反例。但有限数据只能否定错误规则，不能代替对全部输入的证明。

2.2 交换论证的四个步骤

区间调度的证明可以抽象成四步：

  1. 任取一个最优解；
  2. 若它没有采用当前的贪心选择，找到需要替换的对象；
  3. 把贪心选择换入最优解；
  4. 证明交换后仍然合法，并且目标值没有变差。

交换后得到的方案仍是最优方案，而且包含当前贪心选择。接下来还要检查：固定这个选择后，剩余问题是否仍与原问题具有相同结构。只有这一点成立，才能对后续选择重复同样的论证。

交换论证必须同时检查合法性和目标值。只说明“两个方案数量相同”，却没有说明替换后是否违反限制，证明并不完整。

2.3 不同问题需要不同证明方式

交换论证并不是贪心的唯一证明方法。常见思路还包括：

  • 相邻交换：证明任何逆序都能交换成正确顺序，且答案不变差；
  • 下界匹配：证明任何方案至少要付出某个代价，而算法恰好只付出这些代价；
  • 固定前缀：处理完第 ii 个对象后，证明当前前缀已经最优，并且不会再被后续操作修改。

后面的排队接水使用相邻交换，小 A 的糖果则同时使用不可避免的删除量和固定前缀。证明方式取决于选择规则产生的结构，不能看到排序或单向扫描就直接认定它是正确的贪心。

3. 相邻交换：排队接水

例题：排队接水。

题意概述：有 nn 个人排队使用同一个服务窗口，第 ii 个人需要 tit_i 单位时间。一个人的等待时间不包括自己的服务时间。安排队伍顺序，使平均等待时间最小；若两个人用时相同，编号较小者排在前面。

数据范围为 1≤n≤10001\le n\le 1000，1≤ti≤1061\le t_i\le 10^6。

平均等待时间等于总等待时间除以人数，而人数固定，因此只需最小化总等待时间。枚举所有排列需要检查阶乘级数量的方案，无法处理本题范围。

3.1 从两个人的先后顺序推出排序规则

设队伍中相邻两人的服务时间分别为 a,ba,b，在他们之前已经累计了 TT 单位服务时间。

若先安排 aa，再安排 bb，这两人的等待时间之和为

T+(T+a)=2T+a.T+(T+a)=2T+a.

若交换顺序，先安排 bb，再安排 aa，等待时间之和为

T+(T+b)=2T+b.T+(T+b)=2T+b.

排在这两人之后的顾客都需要等待 a+ba+b，不会受到两人内部顺序的影响。因此，当 a≤ba\le b 时，把服务时间较短的人放在前面不会使总等待时间增加。

若一个队伍中存在相邻逆序，即前一人的服务时间大于后一人，就可以交换这两人并减小总等待时间。不断消除逆序后，服务时间从小到大排列，所以升序方案最优。

例如服务时间为 3,1,23,1,2 时，原顺序的总等待时间为 0+3+4=70+3+4=7；升序排列为 1,2,31,2,3 后，总等待时间为 0+1+3=40+1+3=4。

3.2 实现排序与等待时间累加

结构体同时保存服务时间与原编号。服务时间相同时按编号升序排列，这个并列规则不改变最小等待时间，但能满足题目的输出要求。

struct Person
{
    int id, t;
};

bool cmp(const Person &x, const Person &y)
{
    if (x.t != y.t)
    {
        return x.t < y.t;
    }
    return x.id < y.id;
}

sort(a + 1, a + n + 1, cmp);

long long elapsed = 0, total = 0;
for (int i = 1; i <= n; ++i)
{
    if (i > 1)
    {
        cout << ' ';
    }
    cout << a[i].id;

    // 当前人的等待时间等于前面所有人的服务时间之和
    total += elapsed;
    elapsed += a[i].t;
}
cout << '\n';
cout << fixed << setprecision(2) << 1.0 * total / n << '\n';

扫描到第 ii 个人之前，elapsedelapsed 保存前 i−1i-1 个人的服务时间之和，也就是第 ii 个人的等待时间。因此必须先把 elapsedelapsed 加入 totaltotal，再累加当前人的服务时间。

总等待时间最大可达到约 5×10115\times 10^{11}，应使用 long long\texttt{long long}。排序需要 O(nlog⁡n)O(n\log n) 时间，扫描需要 O(n)O(n) 时间，保存队伍需要 O(n)O(n) 空间。

相邻交换推出的排序规则依赖于目标函数。若每个人的等待代价不同，交换前后的差值会发生变化，不能直接继续按服务时间排序。

4. 固定前缀：小 A 的糖果

例题：小 A 的糖果。

题意概述：有 nn 个糖果盒，第 ii 个盒子中有 aia_i 颗糖。每次可以从任意一个盒子中吃掉一颗糖。求至少需要吃掉多少颗糖，才能使任意两个相邻盒子的糖果数之和都不超过 xx。

数据范围为 2≤n≤1052\le n\le 10^5，0≤x,ai≤1090\le x,a_i\le 10^9。

相邻限制只连接连续两个盒子，适合从左向右固定已经处理好的前缀。不过，在决定从哪一个盒子删糖前，需要先处理单盒上界。

4.1 先删除必然无法保留的糖果

任意盒子都与至少一个盒子相邻，糖果数又不会为负。如果最终满足相邻两盒之和不超过 xx，每个盒子本身也一定不超过 xx。因此，盒子中超过 xx 的部分无论如何都必须删除，可以先统一删去。

完成这一步后，每个盒子都有 ai≤xa_i\le x。从左向右检查相邻两盒时，若

ai−1+ai>x,a_{i-1}+a_i>x,

设超出量为

d=ai−1+ai−x.d=a_{i-1}+a_i-x.

任何合法方案都必须从这两个盒子中合计删除至少 dd 颗糖。因为 ai−1≤xa_{i-1}\le x，所以 d≤aid\le a_i，可以把这 dd 颗全部从右侧的第 ii 个盒子删除。

这样既用最少的删除量修复了当前相邻对，又减小了下一对中的左侧盒子，不会给后续制造额外困难。已经处理过的左侧相邻关系不会再改变。

例如 a=[2,5,4]a=[2,5,4]、x=6x=6。第一对超出 11，从第二盒删除 11 颗，序列变为 [2,4,4][2,4,4]；第二对超出 22，从第三盒删除 22 颗，得到 [2,4,2][2,4,2]。总共删除 33 颗。

4.2 实现与前缀不变量

以下数组使用 long long\texttt{long long}，这样相邻和与总删除量都不需要额外转换类型。

long long ans = 0;

// 单盒超过 x 的部分在任何合法方案中都无法保留
for (int i = 1; i <= n; ++i)
{
    if (a[i] > x)
    {
        ans += a[i] - x;
        a[i] = x;
    }
}

// 处理完位置 i 后，前 i 个盒子中的所有相邻限制都已满足
for (int i = 2; i <= n; ++i)
{
    if (a[i - 1] + a[i] > x)
    {
        long long d = a[i - 1] + a[i] - x;
        a[i] -= d;
        ans += d;
    }
}

第二个循环处理完位置 ii 后，前 ii 个盒子中的所有相邻限制都已满足，后续操作只会修改位置 i+1i+1 及其右侧，不会破坏这个前缀。

对于当前相邻对，超出的 dd 颗是任何方案都必须付出的代价。若某个最优方案把其中一部分删除安排在左盒，可以把这部分删除移动到右盒：当前两盒的总数不变，算法此前已经保证左边的相邻关系在恢复左盒后仍然合法，而右盒变小只会有利于下一对。于是总能把一个最优方案调整为当前算法的选择。

两个循环都只扫描数组一次，时间复杂度为 O(n)O(n)，保存数组需要 O(n)O(n) 空间。总删除量可能达到 101410^{14}，答案必须使用 long long\texttt{long long}。

5. 简单构造：按奇偶性分组

考虑下面的任务：重新排列 11 至 nn，使任意两个相邻数之差的绝对值都大于 11。输出任意一种方案；无法做到时报告无解。数据范围为 1≤n≤1051\le n\le 10^5。

这道题不要求比较多个合法方案的优劣，只要生成一个满足限制的排列即可。证明目标也随之改变：不需要证明“当前选择属于某个最优解”，而要证明输出没有遗漏、没有重复，并且每一处相邻关系都合法。

5.1 从禁止条件寻找稳定模式

限制只禁止差为 11 的数相邻。两个不同的偶数之差至少为 22，两个不同的奇数之差也至少为 22。因此可以先升序输出全部偶数，再升序输出全部奇数。

这个方案包含三类需要检查的位置：

  • 偶数组内部：相邻两数之差为 22；
  • 奇数组内部：相邻两数之差为 22；
  • 两组交界：当 n≥4n\ge4 时，最后一个偶数至少为 44，第一个奇数为 11，差至少为 33。

例如 n=5n=5 时，可以输出

2,4,1,3,5.2,4,1,3,5.

当 n=1n=1 时，没有相邻位置，直接输出 11。当 n=2n=2 或 n=3n=3 时，数字 22 与其他所有可选数字的差都为 11，无法把它放入一个合法排列，所以无解。

5.2 生成并输出方案

if (n == 1)
{
    cout << 1 << '\n';
}
else if (n <= 3)
{
    cout << "NO\n";
}
else
{
    vector<int> ans;
    for (int x = 2; x <= n; x += 2)
    {
        ans.push_back(x);
    }
    for (int x = 1; x <= n; x += 2)
    {
        ans.push_back(x);
    }

    for (int i = 0; i < n; ++i)
    {
        if (i > 0)
        {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << '\n';
}

两个循环分别加入所有偶数和所有奇数，每个 11 至 nn 的整数恰好出现一次。生成与输出都需要 O(n)O(n) 时间，数组需要 O(n)O(n) 空间；若直接分两段输出，额外空间可以降为 O(1)O(1)。

构造中常见的奇偶分组、按余数分类、两类元素交替和短周期重复都只是候选模式。使用一种模式时，需要分别检查组内、组间交界、小规模无解情况，以及末尾不足一个完整周期时的情况。

6. 贪心与构造的区别

比较项贪心构造
任务目标在合法方案中求最优值输出任意一个合法方案
核心问题为什么当前选择不会排除所有最优解为什么输出覆盖全部限制
常见证明交换论证、相邻交换、下界匹配、固定前缀分类验证、模式验证、边界与无解证明
常见实现排序、扫描、双指针、堆分组、交替、分块、按周期生成
失败信号能构造出局部选择更好、整体答案更差的反例出现重复、遗漏、非法交界或未覆盖的小规模

排序、双指针和堆只是实现选择顺序的工具，不会自动保证贪心正确；同样，一个构造在若干样例上成立，也不能代替对所有位置和全部规模的验证。

7. 本章小结

  • 贪心规则必须说明当前选择、剩余问题和最优性依据。
  • 交换论证通过改造一个最优解，证明至少存在一个最优解采用当前选择。
  • 相邻交换适合从两个对象的先后贡献中推导排序关键字。
  • 从左向右扫描时，可以用前缀不变量说明已处理部分不会被后续操作破坏。
  • 反例用于排除错误规则和确定适用范围，有限测试不能代替证明。
  • 构造不要求最优，但必须验证元素完整性、全部约束、组间交界和小规模情况。

8. 作业

巩固练习

《纪念品分组》可以先用首尾双指针实现，再补充证明：每轮为什么可以固定当前最贵物品的安排，以及允许每组三件物品后原论证为何失效。

提高训练

完成练习时，应分别写出贪心选择、正确性依据、复杂度和失效条件；构造题还应单独检查无解规模与所有交界位置。