第 47 章　贪心¶

本章配套 18 道例题，见 §例题。

贪心是「每一步都取当前最优」。它的代码通常只有几行，难点 100% 在于证明它是对的。

贪心题的正确打开方式：先猜策略 → 再证明（或至少找不到反例）→ 最后写代码。跳过第二步是笔试丢分的头号原因——错误的贪心往往能过样例。

1　贪心什么时候成立¶

一个问题能用贪心，通常需要两条性质之一：

性质	含义
贪心选择性质	存在一个最优解包含「当前的贪心选择」
最优子结构	做完这次选择后，剩下的子问题的最优解 + 本次选择 = 原问题最优解

第一条是关键，也是交换论证要证的东西。

贪心与 DP 的分界：

	贪心	DP
决策	每步只取一个，不回头	保留所有可能，最后择优
复杂度	通常 \(O(n\log n)\)	通常 \(O(n \cdot V)\) 以上
正确性	需要证明	只要状态定义对就一定对
失败表现	样例过、大数据 WA	TLE / MLE

拿不准的时候，先写 DP 保底，再想能不能贪。反过来（先贪心再补 DP）常常会因为「样例过了」而误判。

2　三种证明手法¶

手法一：交换论证（exchange argument）—— 最常用¶

套路：假设存在一个最优解 \(\mathrm{OPT}\) 不含这个贪心选择，证明可以把 \(\mathrm{OPT}\) 里的某个选择换成贪心选择而不变差。于是「存在一个包含贪心选择的最优解」，归纳即可。

纪念品分组（过河问题）的证明是标准范例：

贪心策略：最重的 \(M\) 和最轻的 \(m\) 能上一条船就上。 正确性：若最优方案里 \(M\) 和 \(m\) 没同船，分两种情况： ① 若 \(M\)（或 \(m\)）单独一条船，让 \(M\) 与 \(m\) 同船不会变差； ② 若 \(M\) 与 \(m'\) 同船、\(M'\) 与 \(m\) 同船，因为 \(M\) 最重、\(m\) 最轻，有 \(M' + m' \le M + m' \le w\)，所以交换 \(m\) 与 \(m'\) 后两条船仍然合法。

手法二：邻项交换（推排序规则）¶

当问题是「给 \(n\) 个物品排个序，代价由顺序决定」时， 比较相邻两个物品交换前后的代价差，就能直接得到排序键。

通用推导步骤：

设相邻两项为 \(i, j\)，把与它们无关的量记成常数 \(P\)；
写出「\(i\) 在前」和「\(j\) 在前」的代价；
令「\(i\) 在前更优」，化简成 \(f(i) < f(j)\) 的形式；
按 \(f\) 升序排序。

# 推出规则后的实现（以「按 a*b 升序」为例）
# key 必须是能比较大小的单个值：排序只保证「相邻两项不该交换」，全序才能推出全局最优
items.sort(key=lambda t: t[0] * t[1])

必须验证 \(f\) 是全序（满足传递性），否则排序结果没有意义。少数题目的比较规则不能写成单元素 key（比如拼接最大数），那时才用 functools.cmp_to_key，见自定义排序 §8。

本章的 BISHI53（按 \(a_i b_i\) 升序）和 BISHI54（按 \(w_i/c_i\) 降序）都是这个套路。

手法三：反证 / 上界构造¶

先证明答案有某个上界（或下界），再构造出一个达到它的方案，两头夹逼。 BISHI44「和为偶数的最大子集」就是：总和是显然上界，只要说明「最多扔掉一个最小奇数」就能达到调整后的上界。

3　经典贪心模型速查¶

模型	策略	证明手法	复杂度
区间调度（选最多不重叠区间）	按右端点升序，能选就选	交换论证	\(O(n\log n)\)
区间覆盖（最少区间覆盖 \([L,R]\)）	每次选「左端合法且右端最远」的	交换论证	\(O(n\log n)\)
带截止期的调度（最多完成几个）	按 deadline 升序 + 大根堆反悔	交换论证	\(O(n\log n)\)
Huffman 编码（最小合并代价）	每次合并最小的两个（小根堆）	交换论证	\(O(n\log n)\)
排序不等式 / 邻项交换	按推出的 \(f\) 排序	邻项交换	\(O(n\log n)\)
两端配对（过河、田忌赛马）	排序后对撞指针	交换论证	\(O(n\log n)\)
前缀容量约束下选最大权	小根堆维护「当前选中集合」	拟阵 / 交换论证	\(O(n\log n)\)
反悔贪心（股票买卖）	堆 + 「压两次」造反悔票	构造双射	\(O(n\log n)\)

这张表覆盖了笔试里 90% 的贪心题，剩下的 10% 基本是「模型 + 一个小变形」。

4　反悔贪心：贪心的进阶形态¶

普通贪心「一步定终身」，反悔贪心允许撤销之前的选择，用堆来维护「最该撤销的那个」。

两种标准形态：

形态一：容量满了就换掉最差的¶

import heapq

h = []                              # 小根堆，存当前已选中的元素；h[0] 就是其中最差的那个
for x in items:
    if len(h) < cap:                # 还没选满，直接收下
        heapq.heappush(h, x)
    elif h and x > h[0]:            # 选满了：只有比最差的更好才值得换
        heapq.heapreplace(h, x)     # 先弹后压，比 pop + push 少一次堆调整

用于 BISHI49（每通过 \(k\) 关得一个道具）、BISHI52（前 \(k\) 大之和）。

形态二：超限了就丢掉代价最大的¶

import heapq

h = []                              # 大根堆（存负数）：已接下的任务耗时
cur = 0                             # 已接任务的总耗时
for t, d in sorted(jobs, key=lambda j: j[1]):    # 按 deadline 升序，保证先安排早截止的
    cur += t                        # 先无条件接下，之后再决定要不要反悔
    heapq.heappush(h, -t)
    if cur > d:                     # 总耗时越过了当前截止时间，必须丢掉一个
        cur += heapq.heappop(h)     # 丢最耗时的那个：任务数不变而总耗时降幅最大
print(len(h))                       # 堆的大小就是最终接下的任务数

用于 BISHI50 建筑抢修——这正是反悔贪心的标准做法。

Python 的 heapq 只有小根堆。 需要大根堆时存 -x（数值）或 (-key, obj)（元组）。见优先队列与堆。

5　偏序集、Dilworth 定理与导弹拦截¶

这一块值得用大篇幅铺开，因为它是「贪心 = DP = 组合定理」三者打通的枢纽。

定义¶

偏序集 \(P = (S, \le)\)：集合 \(S\) 加上满足自反、反对称、传递的关系 \(\le\)。「偏」的意思是允许两个元素不可比。

概念	定义
链（chain）	两两可比的元素组成的子集
反链（antichain）	两两不可比的元素组成的子集
链覆盖	用若干条不相交的链盖住所有元素
反链覆盖	用若干条不相交的反链盖住所有元素

两个对偶定理¶

Mirsky 定理：最小反链覆盖的反链条数 = 最长链的长度。

Dilworth 定理：最小链覆盖的链条数 = 最长反链的长度。

导弹拦截（NOIP 1999）¶

导弹依次飞来，一套系统的每发炮弹高度不能超过前一发。 ① 一套系统最多拦几颗？② 最少几套系统能全拦下？

把序列看成偏序集：\(i \le j\) 当且仅当 \(i \le j\)（下标）且 \(h_i < h_j\)（高度严格递增）。于是

序列上的对象	偏序集上的对象
单调递增子序列	链
不上升子序列	反链

问题 ①「一套系统最多拦几颗」= 最长不上升子序列 = 最长反链；
问题 ②「最少几套系统」= 把序列拆成最少的不上升子序列 = 最小反链覆盖，由 Mirsky 定理 等于最长链 = 最长严格递增子序列。

所以两问的答案分别是「最长不上升子序列」和「最长严格上升子序列」—— 这个漂亮结论完全不需要贪心的直觉，纯靠定理。

换个角度：问题 ② 也可以直接用 Dilworth 定理—— 在反过来定义的偏序集上，最小链覆盖 = 最长反链。一条值得专门提醒的事：\((S,\le)\) 与 \((S,>)\) 这对偏序集下两个定理几乎等价， 但对一般偏序集（比如整除关系）并不总能这样对偶，因为 \(\nmid\) 不满足传递性。

实现¶

求 LIS 的 \(O(n\log n)\) 做法（bisect + 「各长度的最小结尾」数组）本身就是「贪心 + 二分」的组合：

from bisect import bisect_left, bisect_right

def lis_strict(a):
    """最长严格上升子序列的长度，O(n log n)。"""
    tails = []                         # tails[i]：长度为 i+1 的上升子序列里，最小的那个结尾值
    for x in a:
        # tails 恒为严格递增，才有资格上 bisect
        # bisect_left 找第一个 >= x 的位置：等于 x 的不能接在 x 前面，所以严格上升用 left
        i = bisect_left(tails, x)      # 严格上升用 bisect_left
        if i == len(tails):
            tails.append(x)            # x 比所有结尾都大，可以把最长长度再推进一位
        else:
            tails[i] = x               # 用更小的数替换，给后面留空间
    return len(tails)                  # 长度是对的，但 tails 本身不是任何一个真实子序列


def lis_non_decreasing(a):
    """最长不下降子序列：把 bisect_left 换成 bisect_right。"""
    tails = []
    for x in a:
        i = bisect_right(tails, x)     # 找第一个 > x 的位置：等于 x 的可以接续，所以用 right
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

求最长不上升子序列：把序列取负后求最长不下降子序列。

要求的子序列	做法
最长严格上升	`bisect_left`
最长不下降	`bisect_right`
最长严格下降	取负后求最长严格上升
最长不上升	取负后求最长不下降

tails 数组里存的不是任何一个真实的子序列，它只是「长度为 \(i+1\) 的上升子序列中，结尾最小的那个值」。要还原方案得另记前驱。

偏序集的完整理论、Hasse 图、Mirsky 定理的证明见偏序集与Dilworth定理； LIS 的 DP 视角见线性DP。

6　例题¶

题号	题名	难度	题解
BISHI43	讨厌鬼进货	入门	题解
BISHI44	灵异背包？	简单	题解
BISHI45	小红的矩阵染色	简单	题解
BISHI46	小红的魔法药剂	简单	题解
BISHI47	交换到最大	简单	题解
BISHI48	小红的整数配对	简单	题解
BISHI49	小红闯关	中等	题解
BISHI50	[JSOI2007]建筑抢修	中等	题解
BISHI51	低买高卖	中等	题解
BISHI52	奥赛组队	中等	题解
BISHI53	[P1080] 国王游戏(简化版)	中等	题解
BISHI54	货物堆放	中等	题解
BISHI9	田忌赛马	中等	题解
BM95	分糖果问题	较难	题解
BM96	主持人调度（二）	中等	题解
LC45	跳跃游戏 II	中等	题解
LC55	跳跃游戏	中等	题解
LC763	划分字母区间	中等	题解

BISHI43　讨厌鬼进货（入门）¶

\(n\) 种货物，第 \(i\) 种可在 A 家花 \(a_i\)、B 家花 \(b_i\) 买；也可以花 \(x\) 元一次性网购全部 \(n\) 种（不能拆分）。求最小总花费。题面见原题。

网购是「全有或全无」：一旦买了，\(n\) 种就全齐了，再买任何东西都是浪费。所以方案只有两类：不网购（每种独立取 \(\min(a_i, b_i)\)）或网购（花 \(x\)）。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); x = int(data[1])
    a = data[2:2 + n]                                    # A 家的 n 个报价
    b = data[2 + n:2 + 2 * n]                            # B 家的 n 个报价
    # 两家可以混着用，所以逐项取便宜的那家，而不是整体二选一
    s = sum(min(int(p), int(q)) for p, q in zip(a, b))   # 每种货物独立取便宜的
    print(min(x, s))                                     # 网购是全有或全无，只需和 s 比一次


main()

逐项取 min，而不是「A 家全买」和「B 家全买」二选一——供应商可以混着用。
别想着「网购 + 单买」混搭：网购已覆盖全部品类，额外购买只增不减。

题解见 solutions/nowcoder/BISHI43/sol.py。

BISHI44　灵异背包？（简单）¶

从 \(n\) 个正整数里任选若干，使和为偶数且最大。可以一个都不选（和为 0）。题面见原题。

名字是幌子，跟背包毫无关系，考的是奇偶性 + 上界构造（§2 手法三）：

全选的总和 \(S\) 是上界；
\(S\) 为偶数 → 直接输出；
\(S\) 为奇数 → 说明奇数元素有奇数个，必须扔掉奇数个奇数才能变偶。扔得越少越好 → 只扔一个，且扔最小的那个奇数。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(v) for v in data[1:n + 1]]
    s = sum(a)                                   # 全选的总和是答案的上界
    if s % 2 == 0:
        print(s)                                 # 已经是偶数，上界可达
    else:
        # 要变偶必须扔掉奇数个奇数元素；扔得越少越好，所以只扔一个，且扔最小的那个
        # 扔偶数元素改变不了奇偶性，只会让和更小，不予考虑
        print(s - min(v for v in a if v % 2))    # 总和为奇 -> 一定存在奇数元素


main()

扔偶数元素改变不了奇偶性，只会让和变小，所以不考虑。
\(S\) 为奇数时一定存在奇数元素（奇数个奇数相加才为奇）， min(...) 的生成器不会为空，不必兜底。
别写 \(O(nS)\) 的背包 DP：\(n \le 10^5\)、\(a_i \le 2\times10^4\)，\(S\) 可到 \(2\times10^9\)。

题解见 solutions/nowcoder/BISHI44/sol.py。

BISHI45　小红的矩阵染色（简单）¶

\(n\times m\ (\le 10^3\times10^3)\) 的矩阵，* 是黑格不可染，o 是空白。最多把 \(k\) 个空白染红，每个「正下方也是红」的红格得 1 分，求最大分数。题面见原题。

先把得分翻译成人话：得分 = 竖直相邻红格对数。黑格把每一列切成若干连续段，在长为 \(L\) 的段里染 \(c\) 个连续格子得 \(c-1\) 分。于是

\[\text{总分} = (\text{用掉的格子数}) - (\text{用到的段数})\]

预算 \(k\) 固定时，要让分数最大就要用满预算且用到的段数最少 → 按段长从大到小填。长度为 1 的段永远白给 0 分还要占 1 个格子，直接跳过。

剩余预算 \(< 2\) 时开新段没有任何收益，立刻 break。
实现技巧：zip(*rows) 转置后 bytes(col).split(b"*") 在 C 层一次切出所有段，避免 \(10^6\) 次 Python 循环。

完整代码见 solutions/nowcoder/BISHI45/sol.py。

BISHI46　小红的魔法药剂（简单）¶

第 \(i\) 种药剂可以花 \(a_i\) 直接买红色，或消耗红色的第 \(b_i\)、\(c_i\) 种合成蓝色。每种药剂只要有任一形态即可，求最小花费。题面见原题。

看着像图上的依赖问题，其实各药剂完全独立：合成用的原料是消耗品，买来就没了，不能同时充当「已拥有第 \(b_i\) 种」的那一瓶。于是

\[\text{答案} = \sum_i \min\big(a_i,\ a_{b_i} + a_{c_i}\big)\]

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(v) for v in data[1:n + 1]]     # a[i]：直接买第 i 种红色药剂的价格
    p = n + 1                               # 配方区起点，每种药剂 2 个 token
    total = 0
    for i in range(n):
        b = int(data[p]) - 1                # 题面 1-indexed，减 1 转成列表下标
        c = int(data[p + 1]) - 1
        p += 2
        cost = a[b] + a[c]                  # 买两瓶原料合成蓝色
        # 原料是消耗品，买来就没了，不能兼作「已拥有第 b 种」，所以各药剂互不影响
        total += a[i] if a[i] < cost else cost
    print(total)


main()

「原料是消耗品」这一句读懂了，题就没了；读漏了就会去写图上 DP。 贪心题的信息量常常全在题面的一个限定词里。

题解见 solutions/nowcoder/BISHI46/sol.py。

BISHI47　交换到最大（简单）¶

每次选一个非首位、非 0 的字符，数值减 1 后与左邻交换。求能得到的字典序最大串。 \(\sum|s| \le 2\times10^5\)。题面见原题。

先把操作翻译成本质：一个字符向左移动 1 格，代价是自身减 1。所以要把偏移量为 \(t\) 的字符 \(d\) 挪到当前位置，写下的值是 \(d - t\)，且需要 \(d \ge t\)。因为 \(d \le 9\)，只需要看前 10 个候选。

贪心：逐位构造答案，每位取 \(d - t\) 最大者；并列时取偏移 \(t\) 最小的—— 选靠左的元素后，夹在中间的元素偏移会整体减 1，未来更便宜，是严格占优的。

窗口大小是 10 不是 9（偏移 \(t \in [0, 9]\)，共 10 个位置）。
用一个最多 10 元素的小缓冲，del buf[best] 自动完成「后面元素偏移 \(-1\)」。在完整列表里删除是 \(O(n)\)，\(|s| = 2\times10^5\) 时会退化。

完整代码见 solutions/nowcoder/BISHI47/sol.py。

BISHI48　小红的整数配对（简单）¶

把数两两配对，要求 \(|a_i - a_j| \le k\)，每对得分 \(a_i \times a_j\)，求最大总分。允许不配对。\(n, k, a_i \le 10^5\)。题面见原题。

排序后从大到小相邻配对：

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = sorted(int(v) for v in data[2:2 + n])
    ans = 0
    i = n - 1                            # 从最大端往小端走，i 始终指向未处理的最大元素
    while i > 0:                         # 剩不到两个就结束
        if a[i] - a[i - 1] <= k:         # 有序数组里，与 a[i] 差距最小的就是它的左邻
            ans += a[i] * a[i - 1]       # 交换论证保证「最大的两个配一起」不劣
            i -= 2                       # 两个都用掉了
        else:
            i -= 1                       # 与最近的都配不上，与更小的更配不上，只能丢弃
    print(ans)


main()

交换论证：若最优解里 \(a_{n-1}\) 配 \(x\)、\(a_{n-2}\) 配 \(y\)，交换成 \((a_{n-1}, a_{n-2})\) 与 \((x, y)\)，收益变化为

\[a_{n-1}a_{n-2} + xy - a_{n-1}x - a_{n-2}y = (a_{n-1}-y)(a_{n-2}-x) \ge 0\]

不会变差；而 \(x, y\) 都落在长度 \(k\) 的区间内，所以 \(|x - y| \le k\)，新配对合法。

必须从大端开始配。从小端开始在 [3,4,5], k=1 上就会出错（12 vs 20）。
配不上就丢弃：\(a_{n-1}\) 与更小的数差距只会更大，它必然孤立。

题解见 solutions/nowcoder/BISHI48/sol.py。

BISHI49　小红闯关（中等）¶

顺序通过 \(n\) 关，第 \(i\) 关耗时 \(a_i\)。每通过 \(k\) 关得一个跳关道具，用道具可零耗时通过任意一关（跳关也算通过一关）。求最短总时间。题面见原题。

先把约束写清楚：走到第 \(i\) 关之前已通过 \(i-1\) 关，手上有 \(c_i = \lfloor (i-1)/k \rfloor\) 个道具，因此

\[\text{前 } i \text{ 关里被跳过的关数} \le c_i\]

目标是最大化被跳关卡的时间和——这是典型的「前缀容量约束下选最大权子集」，用小根堆在线维护（§4 形态一）：

import sys
from heapq import heappush, heappushpop


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = [int(v) for v in data[2:2 + n]]

    heap = []                       # 小根堆：当前决定跳过的关卡耗时，堆顶是其中最小的
    total = 0                       # 一关不跳时的总耗时
    for i in range(1, n + 1):       # i 是 1-indexed 关号，对应 a[i-1]
        t = a[i - 1]
        total += t
        # 走到第 i 关之前已通过 i-1 关，故手上有 ⌊(i-1)/k⌋ 个道具；写成 i//k 会多算一个
        cap = (i - 1) // k          # 进入第 i 关之前手上的道具数
        if len(heap) < cap:
            heappush(heap, t)       # 容量还有富余，先收下
        elif cap and t > heap[0]:   # cap 为 0 时一个都不能跳，必须挡住
            heappushpop(heap, t)    # 容量满了，换掉最小的那个
    print(total - sum(heap))        # 被跳过的关卡耗时归零，从总时间里扣掉


main()

容量是 \(\lfloor (i-1)/k \rfloor\) 而不是 \(\lfloor i/k \rfloor\)：进第 \(i\) 关时第 \(i\) 关还没通过。写错样例 1 就会输出 1 而不是 4。
跳关也算通过一关（样例 3 在专门考这个：\(k=1\) 时打完第一关后面全能跳）。
合法性：任一前缀 \(i\) 处，最终被选中的元素当时都还在堆里，而堆大小 \(\le c_i\)。容量非减 + 每次只淘汰当前最小者，是标准的交换论证。

题解见 solutions/nowcoder/BISHI49/sol.py。

BISHI50　[JSOI2007] 建筑抢修（中等）¶

\(n \le 1.5\times10^5\) 个建筑，第 \(i\) 个需修 \(t_i\) 秒且必须在 \(d_i\) 秒内修完，一次只能修一个。求最多修好几个。题面见原题。

这题是反悔贪心的模板题：

「如果当前修房任务无法安排进去，那至少也要看看有没有比自己更耗时的任务。如果有的话，就用自己将之前安排的最耗时的任务替换掉。」

import sys
from heapq import heappush, heappop


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    jobs = []
    p = 1
    for _ in range(n):
        t = int(data[p]); d = int(data[p + 1]); p += 2
        jobs.append((d, t))           # 存成 (d, t)，让 sort 直接按截止时间排
    jobs.sort()                       # 按截止时间升序

    heap = []                         # 大根堆（存负数）：已接下的任务耗时
    cur = 0                           # 已接任务的总耗时，也是当前时刻
    for d, t in jobs:
        cur += t                      # 先无条件接下，再看要不要反悔
        heappush(heap, -t)
        if cur > d:                   # 注意是 >：cur == d 表示恰好卡点完成，算成功
            cur += heappop(heap)      # 弹出耗时最大的（存的是负数，取负后最小）
                                      # 弹出的可能正是刚接的这个，那说明它本就不该修
    print(len(heap))                  # 每轮至多弹一个，堆的大小即最终修好的数量


main()

三个要点：

为什么按 \(d\) 排序：若可行解里 \(d\) 大的排在 \(d\) 小的前面，交换这两个任务不会让任何一个超时（交换论证）。所以总存在一个按 \(d\) 升序执行的最优解。
判定是 cur > d（取等号也算成功）。样例里恰好有 1300 == 1300 的边界，写成 >= 就会少算一个。
弹出的可能正是当前这个任务（说明它太长，不如不修），逻辑上完全正确，不用回退指针。

题解见 solutions/nowcoder/BISHI50/sol.py。

BISHI51　低买高卖（中等）¶

已知 \(n \le 3\times10^5\) 天股价，每天至多买/卖 1 股，不能做空，最后必须清仓。求最大收益。题面见原题。

反悔贪心的最精妙形态（CF865D）。维护小根堆存「可以被卖掉的买入价」：

import heapq
import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    ans = 0
    h = []                      # 小根堆：可以被今天卖掉的「买入价」候选
    push, pop = heapq.heappush, heapq.heappop     # 提前绑定，省掉 3e5 次属性查找
    for tok in data[1:n + 1]:
        p = int(tok)
        if h and h[0] < p:      # 堆里最便宜的买入价低于今天的价格，成交有利可图
            ans += p - pop(h)
            # 压第一次：反悔票。若日后出现更高价 q，用它成交会再加 q-p，
            # 两笔合并成 (p-t) + (q-p) = q-t，等价于当初那股留到第 q 天才卖
            push(h, p)          # 反悔票：允许把这笔交易的卖出价往后挪
        push(h, p)              # 压第二次：p 自身也可以充当未来的买入价
    sys.stdout.write(str(ans) + "\n")


main()

「压两次」是全题的灵魂：

第一次压 p 是反悔票。若以后出现更高价 \(q\)，用它成交时会再加 \(q - p\)，两笔合起来是 \((p - t) + (q - p) = q - t\)，等价于「当初那股其实该留到 \(q\) 天再卖」。
第二次压 p 是因为 \(p\) 本身也可以当未来的买入价。

只压一次就退化成「只能做一笔交易」的错解。

「第 \(n\) 天必须清仓」不需要额外处理：每笔收益都由一买一卖配对产生，堆里剩下的都是从没成交过的价格，天然平仓。

题解见 solutions/nowcoder/BISHI51/sol.py。

BISHI52　奥赛组队（中等）¶

\(n \le 3000\) 名学生各有编程能力 \(a_i\)、体育能力 \(b_i\)。选 \(p\) 人进编程队、\(s\) 人进体育队（不重叠），最大化 \(\sum a + \sum b\)，并输出方案。题面见原题。

关键引理（交换论证）：若最优解里 \(i\) 进编程队、\(j\) 进体育队，且 \(a_i - b_i < a_j - b_j\)，把两人对调，总实力变化

\[(a_j + b_i) - (a_i + b_j) = (a_j - b_j) - (a_i - b_i) > 0\]

与最优矛盾。所以最优解中编程队每人的 \(a-b\) 都不小于体育队每人的 \(a-b\)。

于是按 \(a_i - b_i\) 降序排序后，一定存在分界点 \(t\)：编程队全在前 \(t\) 个、体育队全在后 \(n-t\) 个。枚举 \(t\)，用两个大小固定的堆分别维护「前缀里 \(a\) 最大的 \(p\) 个之和」和「后缀里 \(b\) 最大的 \(s\) 个之和」即可。

排序键写反（升序）直接错。
\(p\) 或 \(s\) 可能为 0，堆维护里要挡住。
答案不唯一，本题配了 special judge。

完整代码见 solutions/nowcoder/BISHI52/sol.py。

BISHI53　[P1080] 国王游戏（简化版）（中等）¶

国王固定在最前，\(n \le 60\) 位大臣可任意排序。第 \(i\) 位大臣得到 \(\left\lfloor \dfrac{\prod_{j<i} a_j}{b_i} \right\rfloor\) 枚金币。最小化「拿得最多的那位大臣」的金币数。\(a_i, b_i \le 8\)。题面见原题。

邻项交换的教科书题。设相邻两位大臣 \(i, j\)，前面所有人的左手乘积为 \(S\)：

排法	两人分别拿到
\(i\) 在前	\(S / b_i\)，\(S a_i / b_j\)
\(j\) 在前	\(S / b_j\)，\(S a_j / b_i\)

两种排法的最大值分别由 \(S a_i / b_j\) 与 \(S a_j / b_i\) 主导（另一项恒更小），比较即得：\(i\) 在前更优 \(\iff a_i b_i < a_j b_j\)。按 \(a_i b_i\) 升序排。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a0 = int(data[1])                 # 国王的左手数，data[2] 是国王的右手数 b0，用不到
    pairs = []
    for i in range(n):
        # 大臣数据从下标 3 开始，每人 2 个 token
        a = int(data[3 + 2 * i])
        b = int(data[4 + 2 * i])
        pairs.append((a * b, a, b))   # 把排序键放在元组首位，sort 直接按它比较
    pairs.sort()                      # 按 a*b 升序（邻项交换推出的规则）

    prefix = a0                       # 当前大臣前面所有人的左手乘积
    ans = 0
    for _, a, b in pairs:
        v = prefix // b               # 先算金币再累乘，保证 prefix 不含自己的 a
        if v > ans:
            ans = v                   # 要的是「拿得最多的那位」，全程取最大值
        prefix *= a                   # 8^60 量级的大整数，Python 的 int 直接扛
    sys.stdout.write(str(ans) + "\n")


main()

这题真正的难点在 C++ 那边：\(\prod a_i\) 最大到 \(8^{60} \approx 1.8\times10^{54}\)， 必须写高精度乘法和高精度除单精。 Python 的 int 是任意精度的，于是整道 NOIP 提高组题退化成一次排序 + 一遍累乘。 这是 Python 选手在 OI 题上最大的一次「白嫖」，见高精度与大整数。

题解见 solutions/nowcoder/BISHI53/sol.py。

BISHI54　货物堆放（中等）¶

\(n \le 10^5\) 件货物竖直堆放，第 \(i\) 件被上方总重 \(W_i\) 压后体积为 \(v_i - c_i W_i\)。安排顺序使 \(\sum v_i'\) 最小。题面见原题。

\(\sum v_i\) 是常数，所以「最小化总体积」= 「最大化 \(\sum c_i W_i\)」。邻项交换：设相邻两件 \(i, j\) 上方总重为 \(P\)，

排法	两者贡献
\(i\) 在上	\(c_i P + c_j (P + w_i)\)
\(j\) 在上	\(c_j P + c_i (P + w_j)\)

作差得 \(c_j w_i - c_i w_j\)。要它 \(> 0\)（\(i\) 放上面更优）即 \(c_j w_i > c_i w_j\)，也就是按 \(w_i / c_i\) 降序排——又重、又不易被压缩的货物放最上面。

排序键的精度问题是这题的隐藏考点。用浮点 w / c 有误差风险，更稳的是精确整数键：

key = (w << 128) // c            # 把比值放大 2^128 再截断，量化步长 3e-39

两个不同比值的最小间隔是 \(1/(c_1 c_2) \ge 10^{-24}\)，远大于量化步长，所以整数键严格保序。\(c_i\) 可以为 0（永不被压缩），比值视作 \(+\infty\)，用一个哨兵 1 << 200 排最前。

比 functools.cmp_to_key 快得多：后者要 \(O(n\log n)\) 次 Python 层调用，前者只是一次大整数移位 + 整除，\(n = 10^5\) 实测 0.16 秒。见自定义排序 §8。

完整代码见 solutions/nowcoder/BISHI54/sol.py。

BISHI9　田忌赛马（中等）¶

三局两胜，速度严格大于才算赢。已知齐威王三匹马的出场顺序，田忌可任意调整自己三匹马的顺序，问能否获胜。\(1 \le v_i, a_i \le 9\)。题面见原题。

这题挂着贪心的名字，正解却是暴力枚举：\(n = 3\) 固定，只有 \(3! = 6\) 种出场顺序。

from itertools import permutations

v = list(map(int, input().split()))     # 齐威王的出场顺序，固定不动
a = list(map(int, input().split()))     # 田忌的三匹马，可任意重排

# 枚举田忌三匹马的全部 3! = 6 种出场顺序；严格大于才算赢，平局不计入任何一方
# 三局两胜等价于「赢的局数 >= 2」，所以只数 x > y 的局数
ok = any(sum(x > y for x, y in zip(p, v)) >= 2 for p in permutations(a))
print("Yes" if ok else "No")

「严格大于」才算赢，相等是平局，不计入任何一方。
三局两胜 = 赢的局数 \(\ge 2\)，平局不能算赢（样例 2 的 2 2 2 vs 2 2 3 输出 No）。

那么经典的田忌赛马贪心是什么？ 当 \(n\) 一般大时（两边各 \(n\) 匹马，求最多赢几局），标准策略是排序后对撞指针：

# [片段] n 匹马版本的经典贪心（本题 n=3，用不上）
a.sort(); v.sort()   # 对撞指针的前提：两边都有序，才有「往左更慢、往右更快」的单调性
i = j = 0            # 田忌 / 齐王 的最慢马
x = y = n - 1        # 田忌 / 齐王 的最快马
win = 0
while i <= x:        # 田忌的马从两端往中间取完为止
    if a[x] > v[y]:          # 最快对最快，能赢就赢（赢下最难赢的一局）
        win += 1; x -= 1; y -= 1
    elif a[i] > v[j]:        # 最慢对最慢，能赢就赢（白捡一局）
        win += 1; i += 1; j += 1
    else:                    # 两头都赢不了，用最慢的马去消耗对方最快的马
        if a[i] < v[y]:      # 严格小于才算输一局，相等是平局不扣分
            win -= 1
        i += 1; y -= 1

为什么本题不该写这个贪心：\(n = 3\) 时枚举全排列是 \(O(1)\) 且绝对不会错，而贪心版本要处理「平局怎么算」「三局两胜而非最多赢几局」等一堆边界。 数据规模允许暴力时就暴力——这本身也是一种「贪心」（对自己的调试时间贪心）。

题解见 solutions/nowcoder/BISHI9/sol.py。

面试题单里的两道贪心题¶

主持人调度（二）是 §3 那张表里「区间调度」的变形：给一堆活动的起止时间，问最少要几位主持人。把「最少几个人」换个说法就是「任一时刻最多有几个区间同时覆盖」—— 按起点排序后用小根堆维护「已开始但未结束的活动的结束时间」，新活动开始时把堆顶已结束的都弹掉，堆的最大规模就是答案，\(O(n\log n)\)。另一条等价路是把 \(2n\) 个端点排序后扫描，起点 \(+1\) 终点 \(-1\) 取前缀最大值，本质是前缀和与差分的差分计数。 端点相同时终点必须排在起点前面，否则「上一场刚结束、下一场就开始」会被算成两个人。

分糖果问题是两遍扫描型的贪心：每个孩子至少一颗，相邻两人中评分高的必须拿得更多。做法是先从左到右扫一遍保证「比左邻高就多给一颗」，再从右到左扫一遍取 \(\max\) 保证右侧约束。 两遍都必须做，且第二遍要取 \(\max\) 而不是直接覆盖—— 只扫一遍会让先出现的约束被后出现的破坏，直接覆盖则会毁掉第一遍已经满足的左侧约束。它的正确性用交换论证不好说，更自然的说法是：每个位置的最终值是「它必须满足的两个下界」的较大者，而这个取值同时满足两条约束且不可能更小，所以总和最小。这类「先分方向各扫一遍再合并」的手法在贪心题里很常见。

另一处题库里的三道贪心题¶

LC 55. 跳跃游戏与 LC 45. 跳跃游戏 II：同一个题面，问「能不能」与问「最少几步」的贪心不是一个。 LC55 只问可达性，维护一个「目前能到的最远下标」即可：从左往右扫，当前下标超出这个最远值就说明断了；否则用 i + a[i] 去更新它，\(O(n)\)。 LC45 要最少步数，得再引入当前这一步的边界：扫到边界处就把步数加一、并把边界推到这一段里能达到的最远处。这等价于一次隐式的广搜——每一「步」就是广搜的一层，所以它给出的必是最少步数，而不需要另外证明贪心的正确性。把 LC45 写成「每次跳到能跳最远的那一格」是错的：那是局部最优，真正该比的是「跳过去之后能覆盖到多远」。

LC 763. 划分字母区间：先把约束折算成区间，再做区间贪心。 同一个字母必须落在同一段里，等价于「该字母首次出现到末次出现」这个区间不可切开。于是先扫一遍记下每个字母的末次位置，再扫第二遍维护当前段的右边界，走到边界就切一刀，\(O(n)\) 时间、\(O(26)\) 空间。这道题值得记的是那一步转化：题面说的是字母，约束的却是区间，换完之后它就落进本章区间贪心的模板里了。

7　本章速查¶

模型	策略
选最多不重叠区间	按右端点升序
最少区间覆盖	每次选左端合法且右端最远的
带 deadline 的调度	按 \(d\) 升序 + 大根堆反悔
最小合并代价	Huffman，小根堆
顺序决定代价	邻项交换推排序键
两端配对	排序 + 对撞指针
前缀容量约束选最大权	小根堆，超容量弹最小
股票买卖	反悔贪心，压两次

证明手法	用法
交换论证	假设 OPT 不含贪心选择，换进去不变差
邻项交换	比较相邻两项交换前后的代价差 → 排序键
上界构造	先证上界，再构造达到它的方案

Dilworth / Mirsky	结论
Mirsky	最小反链覆盖数 = 最长链长度
Dilworth	最小链覆盖数 = 最长反链长度
导弹拦截 ①	最长不上升子序列
导弹拦截 ②	最长严格上升子序列
LIS 严格上升	`bisect_left`
LIS 不下降	`bisect_right`
最长不上升	取负后求最长不下降

Python 相关	结论
大根堆	`heapq` 存 `-x`
换掉堆里最小的	`heappushpop` / `heapreplace`
比值排序键	用 `(w << 128) // c` 精确整数键，别用浮点
高精度乘积（国王游戏）	Python 原生 `int`，白嫖

模板	位置
反悔贪心（容量型 / 超限型）	§4
LIS 的 \(O(n\log n)\) 四种变体	§5
田忌赛马通用贪心	§6 BISHI9

第 47 章 贪心¶

1 贪心什么时候成立¶

2 三种证明手法¶

手法一：交换论证（exchange argument）—— 最常用¶

手法二：邻项交换（推排序规则）¶

手法三：反证 / 上界构造¶

3 经典贪心模型速查¶

4 反悔贪心：贪心的进阶形态¶

形态一：容量满了就换掉最差的¶

形态二：超限了就丢掉代价最大的¶

5 偏序集、Dilworth 定理与导弹拦截¶

定义¶

两个对偶定理¶

导弹拦截（NOIP 1999）¶

实现¶

6 例题¶

BISHI43 讨厌鬼进货（入门）¶

BISHI44 灵异背包？（简单）¶

BISHI45 小红的矩阵染色（简单）¶

BISHI46 小红的魔法药剂（简单）¶

BISHI47 交换到最大（简单）¶

BISHI48 小红的整数配对（简单）¶

BISHI49 小红闯关（中等）¶

BISHI50 [JSOI2007] 建筑抢修（中等）¶

BISHI51 低买高卖（中等）¶

BISHI52 奥赛组队（中等）¶

BISHI53 [P1080] 国王游戏（简化版）（中等）¶

BISHI54 货物堆放（中等）¶

BISHI9 田忌赛马（中等）¶