第 47 章　贪心

配套例题：BISHI43 讨厌鬼进货、BISHI44 灵异背包？、BISHI45 小红的矩阵染色、 BISHI46 小红的魔法药剂、BISHI47 交换到最大、BISHI48 小红的整数配对、 BISHI49 小红闯关、BISHI50 [JSOI2007] 建筑抢修、BISHI51 低买高卖、 BISHI52 奥赛组队、BISHI53 [P1080] 国王游戏、BISHI54 货物堆放、BISHI9 田忌赛马 来源：S3 day5《贪心问题选讲》（riteme）全篇，含纪念品分组、导弹拦截、 偏序集与 Dilworth 定理、Bohater、合并果子、建筑抢修

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

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

---

47.1　贪心什么时候成立

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

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

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

贪心与 DP 的分界：

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

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

---

47.2　三种证明手法

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

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

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

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

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

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

通用推导步骤：

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

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

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

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

手法三：反证 / 上界构造

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

---

47.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% 基本是「模型 + 一个小变形」。

---

47.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 建筑抢修——这正是 S3 day5 第 148–152 页讲的做法。

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

---

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

S3 day5 用了近 40 页讲这一块，因为它是「贪心 = 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 定理的证明见 111-偏序集与Dilworth定理； LIS 的 DP 视角见 102-线性DP。

---

47.6　例题

BISHI43　讨厌鬼进货（入门）

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

网购是「全有或全无」：一旦买了，\(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/BISHI43.py。

BISHI44　灵异背包？（简单）

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

名字是幌子，跟背包毫无关系，考的是奇偶性 + 上界构造（47.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/BISHI44.py。

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

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

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

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

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

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

完整代码见 solutions/BISHI45.py。

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

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

看着像图上的依赖问题，其实各药剂完全独立：合成用的原料是消耗品， 买来就没了，不能同时充当「我拥有第 \(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/BISHI46.py。

BISHI47　交换到最大（简单）

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

先把操作翻译成本质：一个字符向左移动 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/BISHI47.py。

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

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

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

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/BISHI48.py。

BISHI49　小红闯关（中等）

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

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

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

目标是最大化被跳关卡的时间和——这是典型的「前缀容量约束下选最大权子集」， 用小根堆在线维护（47.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/BISHI49.py。

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

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

这题就是 S3 day5 第 148–152 页的原题，反悔贪心的模板：

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

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/BISHI50.py。

BISHI51　低买高卖（中等）

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

反悔贪心的最精妙形态（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/BISHI51.py。

BISHI52　奥赛组队（中等）

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

关键引理（交换论证）：若最优解里 \(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/BISHI52.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\)。 题面见 BISHI53 原题（牛客）。

邻项交换的教科书题。设相邻两位大臣 \(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 题上最大的一次「白嫖」，见 22-高精度与大整数。

题解见 solutions/BISHI53.py。

BISHI54　货物堆放（中等）

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

\(\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 秒。见 12-自定义排序 §12.8。

完整代码见 solutions/BISHI54.py。

BISHI9　田忌赛马（中等）

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

这题挂着贪心的名字，正解却是暴力枚举：\(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/BISHI9.py。

---

47.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，白嫖

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