第2章 · 细腻的“暴力”美学——穷举算法与贪心算法

来源、目录与技术核对边界

“第2章 · 细腻的“暴力”美学——穷举算法与贪心算法”以天瓏书店详细书目与目录核对段忠杰、顾业鸣著、中国水利水电出版社、ISBN 9787522615059、245 页以及全书 6 章；该页标出版日期 2023 年 6 月 1 日。河南省政府采购书目记录同一 ISBN、题名、作者和出版社，但出版时间写作 2023 年 5 月。日期口径相差一个月，本课程保留差异，不自行断言哪一天是正式首发日。

对“第2章 · 细腻的“暴力”美学——穷举算法与贪心算法”而言，公开来源只提供书目和详细目录，不含可授权改写的完整正文；本站的解释、推导、代码、交互、练习和答案均为独立教学重写。目录页第 4 章和第 6 章标题存在明显 OCR 或排版异常，站内按上下文规范化标题，但在清单中披露校正。

“第2章 · 细腻的“暴力”美学——穷举算法与贪心算法”的技术事实另以WG21 C++23 最终工作草案中的算法与整数语义复核：技术来源 1。来源用于检查概念、语言语义或历史算法边界，不把现代竞赛规则静默投射成 2023 年原书的逐字内容。

围绕“怎样区分可证明完整的穷举、具有交换论证的贪心与只在样例上成功的捷径？”，先预测正确轨迹，再只注入“看到局部收益最大就直接采用贪心，没有交换论证或最小反例搜索”。若不能用最小反例定位第一处错误决策，就拒绝当前算法解释。

从“暴力就是笨办法”这个误解开始

先预测：面对一个新问题，是直接猜一个看起来聪明的规则更可靠，还是先写出一定正确但可能较慢的解法更可靠？第2章的“暴力”并不粗糙。它把所有合法候选系统地覆盖，为正确性、优化方向和对拍测试提供基准。

的核心不是多写循环，而是回答三个问题：候选空间是什么、怎样保证不重不漏、每个候选怎样验证。只有候选数乘验证成本在预算内，它才是可执行方案。

2.1 穷举算法

穷举的第一价值是正确。第二价值更重要：把重复计算暴露出来后，才能发现哪些状态足以替代完整历史。优化不是凭空出现，而是从完整基线中删除不必要的自由度。

2.1.1 素数判断

素数判断的直接定义是：对整数$n\ge2$，枚举$2$到$n-1$，若存在整除因子则$n$为合数。这个算法不漏因子，但做了大量对称工作。若$n=ab$且$a>\sqrt n$、$b>\sqrt n$，则$ab>n$，矛盾；因此合数必有一个不大于$\sqrt n$的因子。

bool is_prime(long long n) {
    if (n < 2) return false;
    for (long long d = 2; d <= n / d; ++d) {
        if (n % d == 0) return false;
    }
    return true;
}

条件d <= n / d避免直接计算d*d可能发生的整数溢出。循环提前返回是安全的：一旦找到因子，之后候选不可能改变“合数”结论。

2.1.2 关灯游戏

关灯游戏看似每个格子都可按或不按，$r\times c$棋盘有$2^{rc}$种按法。但按键的影响只与奇偶有关，同一格按两次等于没按；更关键的是，一旦第一行按法确定，为了熄灭上一行，第2行到最后一行的选择被逐行强制。

于是只需枚举第一行的$2^c$个bitmask。对每个mask向下模拟，最后检查末行是否全灭：

for (int first = 0; first < (1 << cols); ++first) {
    Board board = initial;
    apply_first_row(board, first);
    for (int row = 1; row < rows; ++row) {
        for (int col = 0; col < cols; ++col) {
            if (board.on(row - 1, col)) board.press(row, col);
        }
    }
    if (board.last_row_is_off()) record_solution(board);
}

搜索量从$O(2^{rc})$降为$O(2^c rc)$。这仍是穷举，却通过“其余决策被首行唯一决定”的结构压缩了候选空间。

2.2 从穷举算法到贪心算法

从穷举算法到贪心算法，需要找到可丢弃的历史。若两个部分解未来的所有可能性相同，只保留当前更优的代表即可；若某个局部选择能交换进任意最优解而不变差，就可以直接固定它。

2.2.1 买卖股票的最佳时机

买卖股票的最佳时机若只允许先买一次、后卖一次，穷举所有$(buy,sell)$对共有：

枚举卖出日$j$时，只需要此前最低买入价，而不需要保存每个买入日。令$m_j=\min_{0\le i<j}p_i$，最佳收益为：

long long max_profit(const std::vector<long long>& price) {
    if (price.size() < 2) return 0;
    long long minimum = price[0];
    long long best = 0;
    for (std::size_t day = 1; day < price.size(); ++day) {
        best = std::max(best, price[day] - minimum);
        minimum = std::min(minimum, price[day]);
    }
    return best;
}

更新顺序表达“必须先买后卖”：先用历史minimum计算今天卖出的收益，再把今天加入未来可买集合。若题目要求必须完成一次亏损交易，best不能初始化为0，contract不同会改变边界实现。

2.2.2 物流站的选址（一）

物流站的选址（一）先从穷举开始：居民位于一条线上，候选站点为整数坐标$x$，目标最小化总距离：

若坐标范围很小，可以枚举所有$x$并计算$F(x)$。这个基线揭示了折线函数的变化：站点向右移动一步，左侧居民距离增加，右侧居民距离减少。最优点在左右数量达到平衡的位置附近。

2.3 贪心算法

必须同时回答：

• Greedy choice是什么？
• 选择后剩余问题是否仍是同类子问题？
• 为什么至少存在一个最优解包含这个选择？

“每次选当前看起来最好”只是候选规则；证明完成后，它才是算法。

2.3.1 物流站的选址（二）

物流站的选址（二）把前一节观察变成结论。将坐标排序为$a_1\le\cdots\le a_n$。若$x$位于中位数左侧，向右移动不会增加左侧距离的速度超过右侧距离减少的速度；越过中位数后方向反转。因此任一中位数最小化绝对距离和。

对偶数$n$，两个中间坐标之间的任意点都最优；若站点必须取居民坐标，可选任一中间坐标。这个规则不是尝试所有站点，而是一次排序加一次取中位数，或用线性选择算法直接找中位数。

2.3.2 回合制游戏

回合制游戏常把“先击败谁”转化为调度。设敌人A需要$t_A$回合击败、每回合造成$d_A$伤害，B类似。只比较相邻两者：

因此A先于B不差，当且仅当$t_A/d_A\le t_B/d_B$。把所有敌人按这个比值排序，任意逆序相邻对都能交换而不增加伤害，最终得到全局最优顺序。

这里使用了。注意除法比较应交叉相乘，避免浮点误差；乘积可能溢出时使用更宽整数。

2.3.3 快递包装

考虑快递包装的一个标准容量模型：每个包装最多装两件，重量不超过$C$，目标最少包装数。排序后查看最重物品$h$：

• 若最轻物品$l$与$h$能同装，就把二者配对；
• 否则任何其他物品都不可能与$h$同装，$h$必须单独包装。

int minimum_parcels(std::vector<int> weight, int capacity) {
    std::sort(weight.begin(), weight.end());
    int parcels = 0;
    std::size_t left = 0;
    std::size_t right = weight.size();
    while (left < right) {
        --right;
        if (left < right && weight[left] + weight[right] <= capacity) ++left;
        ++parcels;
    }
    return parcels;
}

证明分两种：若最轻者也装不下，最重者单独是被迫选择；若能装下，把某个最优解中与最重者同装的物品换成更轻的$l$不会超重，另一件被换出的物品也不会让包装数增加。于是贪心配对可进入某个最优解。

2.4 “暴力”的算法与精妙的结论

“暴力”的算法与精妙的结论之间没有高低之分，而是分工：

最大面值优先找零说明局部直觉会失败。币值$\{1,3,4\}$、金额6时，贪心得到$4+1+1$三枚，而最优是$3+3$两枚。

不仅用于否定。最小反例往往指出证明缺少的结构，例如某些币值系统满足最大面值优先，任意币值系统却不满足。

把穷举变成贪心的验收oracle

小规模穷举可以持续服务于优化后的算法。先把规模限制在可枚举范围，例如数组长度不超过8、坐标值不超过10；再生成全部结构不同的输入，用穷举返回规范化最优值，用候选贪心返回同一目标值。二者一旦不等，就保存输入并继续做delta debugging：删除元素、缩小数值、减少容量，直到得到不能再缩小的反例。这样的最小反例通常直接暴露错误规则依赖了哪个不存在的性质。

验收不能只比较目标值。还要分别检查：贪心输出是否满足容量、顺序等可行性；目标值是否与oracle一致；同一输入重复运行是否稳定；最大规模是否满足预算。若题目允许多个最优解，比较规范化目标值和约束，而不要要求输出序列逐字符相同。

一个完整交换证明有四项义务。第一，局部选择本身可行；第二，任取一个最优解，都能找到第一个与贪心不同的位置；第三，把该位置交换为贪心选择后，约束不被破坏、目标不变差；第四，固定这个选择后，剩余部分仍可按同样论证处理。任何一项说不清，都只能把规则视为待检验猜想。

例如快递包装“最多两件”是交换安全的关键条件。若一个包装可放三件，最轻者与最重者配对可能占用一个本可用于形成三件组合的位置；原证明不再覆盖这种变化。算法结论必须和证明前提一起保存，不能只保留一句贪心口诀。

正式节点与算法证据

• 穷举算法 ：第 1 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 素数判断 ：第 2 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 关灯游戏 ：第 3 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 从穷举算法到贪心算法 ：第 4 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 买卖股票的最佳时机 ：第 5 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 物流站的选址（一） ：第 6 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 贪心算法 ：第 7 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 物流站的选址（二） ：第 8 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 回合制游戏 ：第 9 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 快递包装 ：第 10 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。
• 暴力的算法与精妙的结论 ：第 11 个正式节点要能回到“穷举覆盖所有候选且无重复遗漏，贪心选择具有可说明的安全性或明确反例边界。”，并给出成功输入与失败反例。

小结

本章从素数判断和关灯游戏理解穷举算法的完备性与候选压缩；从买卖股票的最佳时机和物流站的选址（一）观察重复计算；再在物流站的选址（二）、回合制游戏、快递包装中把局部规则升级为有证明的贪心算法。

可靠路径是：先用暴力解建立真值，再找充分状态和强制选择，最后用交换论证或反例完成验收。精妙结论并不来自跳过暴力，而常来自把暴力基线看得足够清楚。

练习与答案

名词解释