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

按图解版第2章重建素数判断、关灯游戏、股票收益、物流站选址、回合制顺序、快递包装，以及从穷举基线到可证明贪心的完整方法。

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

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

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

2.1 穷举算法

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

2.1.1 素数判断

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

n\text{ is composite} \Longrightarrow \exists d,\ 2\le d\le\lfloor\sqrt n\rfloor,\ d\mid 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)$ 对共有：

\binom n2=\frac{n(n-1)}2

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

\max_{1\le j<n}(p_j-m_j)

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$ ，目标最小化总距离：

F(x)=\sum_{i=1}^{n}|a_i-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类似。只比较相邻两者：

\operatorname{cost}(A,B)-\operatorname{cost}(B,A) =t_A d_B-t_B d_A

因此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一致；同一输入重复运行是否稳定；最大规模是否满足预算。若题目允许多个最优解，比较规范化目标值和约束，而不要要求输出序列逐字符相同。

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

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

小结

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

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