从伐木工到二分答案：单调性、整数二分与溢出边界

第一次在题单里翻到这道编号 1908 的"伐木工"，我下意识觉得这是道模拟题——题目描述那么直白，照着砍一遍不就行了？可等我把数据范围那一栏读完，这个念头立刻被打消了。树的数量动辄上万，单棵树的高度又能到九位数，如果老老实实枚举锯片的每一个可能高度，就算机器每秒能跑一亿次运算，也得跑到天荒地老。这道题真正想考的东西藏在场景背后：当你发现"锯片设得越高，能拿到的木材越少"这条规律时，就该意识到这是一道标准的二分答案题。伐木工只是它的外壳，骨架是"在单调函数上求边界"。这篇内容我会把这道题从题意翻译、单调性证明、整数二分写法、溢出与边界，一路讲到排序加前缀和的优化版本，并且附上可运行的代码和一套我自己常用的对拍验证流程。不管你是刚学二分的新手，还是刷题刷到有点麻木、想把这类题彻底吃透的人，都能从这里捞到东西。

1. 别急着写循环——先把"伐木工"翻译成一个函数

1.1 题目里的三样东西：树高、锯片高度、到手木材

这道题描述的场景很朴素：一片林子里有若干棵树，每棵树有各自的高度；伐木工把锯片固定在某一个高度上水平推过去，凡是比锯片高的树，超出锯片的那一截就会被切下来，成为他的收获；比锯片矮的树则一动不动，一根木头都不贡献。

输入通常给两个关键数值：树的棵数 N、需要的木材总量 M，以及 N 棵树各自的高度。要输出的则是伐木工把锯片设在哪一个高度上，能让到手的木材不少于 M，并且这个高度要尽可能大。

为什么是"尽可能大"？这里藏着一个容易被扫过去的约束：锯片设得越低，砍下来的木头越多，但越低的锯片意味着伐木工要贴着地面往下切，作业难度和损耗都上去了。题目用"求最大高度"这个条件，其实是在说"在满足需求的前提下，锯得越省力越好"。这个看似可有可无的附加条件，恰恰是让二分答案能够成立的另一半拼图。如果题目改成"求任意一个可行高度"，那随便给个 0 都能交差，题目也就没意义了。

1.2 f(H) 的数学表达和它的取值范围

把口语描述换成数学语言，这件事立刻变清爽了。设锯片高度为 H，第 i 棵树的高度为 h_i，那么这棵树贡献的木材量就是：

f_i(H) = max(0, h_i - H)

整片林子的总收获就是把每棵树的贡献加起来：

f(H) = Σ max(0, h_i - H) (i 从 1 到 N)

题目要求的就是：在所有满足 f(H) ≥ M 的 H 中，找出最大的那个。

这个函数有几个性质值得先摸清楚，它们直接决定了后面算法的形状。第一，f(H) 的每一项都只跟 H 有关，彼此独立，没有耦合，所以计算 f(H) 只需要一次线性扫描，复杂度 O(N)。第二，每一项 max(0, h_i - H) 都不可能为负，所以 f(H) 恒大于等于 0，而且当 H 取到所有树里最高的那棵时，f(H) 恰好等于 0。第三，也是最关键的一点，H 每增加一点，每一项都不会变大，所以 f(H) 只会往下走或者原地不动。这三点里，前两点帮你确定取值范围，第三点帮你确定算法。

1.3 为什么"枚举所有高度"这条路走不通

新手最自然的想法是：从 0 开始，一个高度一个高度往上试，第一个不满足 f(H) ≥ M 的高度减一就是答案。这个思路逻辑上完全正确，问题出在代价上。

假设树高最大值是 10^9，那么最坏情况下你要试 10^9 个高度，每个高度都要扫一遍 N 棵树。如果 N 是 10^5，总运算量就是 10^14 级别。这个量级别说普通电脑，就是给它一整天也跑不完。即便树高只有 10^5，乘上 10^5 棵树，也是 10^10，依然超时。

真正让人心疼的是，这里面绝大部分计算都是浪费的。因为 f(H) 是单调的，一旦你发现某个高度 H0 不满足条件，那么所有比 H0 大的高度都不必再试了；反过来，一旦某个高度满足条件，所有比它低的高度也都不必再试。也就是说，你每次试探获得的信息量远不止"这一个点行不行"，而是"一整段区间行不行"。枚举把这份信息白白扔掉了，二分则是把它全部收进口袋。

提示：看到"求满足某条件的最优值"并且"条件关于这个值单调"，就该条件反射地想到二分答案，而不是线性扫描。这个判断只需要几秒钟，但它决定了你的程序是 0.1 秒还是 TLE。

2. 单调性才是这道题真正的题眼

2.1 锯片抬高，木材只会变少：单调不增的严格说明

很多讲解会把单调性一笔带过，说句"显然"就过去了。但我更愿意把它老老实实推一遍，因为能证明单调性，才说明你真正理解了这道题为什么能用二分。

取任意两个高度 H1 < H2，要证明 f(H1) ≥ f(H2)。看单棵树：如果 h_i ≤ H1，那么两个高度下这项都是 0，相等；如果 H1 < h_i ≤ H2，那么 f_i(H1) = h_i - H1 > 0，而 f_i(H2) = 0，前者更大；如果 h_i > H2，那么 f_i(H1) = h_i - H1，f_i(H2) = h_i - H2，因为 H1 < H2，所以 h_i - H1 > h_i - H2，前者依然更大。三种情况覆盖了所有可能，每一项都是 f_i(H1) ≥ f_i(H2)，加总起来自然有 f(H1) ≥ f(H2)。

结论就是：f 关于 H 单调不增。注意是"不增"不是"严格递减"。这两者差别很大。当所有树高都是整数、H 也是整数时，f(H) 会是阶梯状下降的，中间可能存在一段平的地方。这一点在讨论"恰好等于 M"的变体时会造成麻烦，后面会专门讲。

2.2 把"求最大高度"翻译成"找最后一个满足条件的点"

单调性一旦确立，问题就换了个面貌。在数轴上从左到右看 H 的取值，每个点要么满足 f(H) ≥ M（记为"可行"），要么不满足（记为"不可行"）。因为 f 单调不增，可行点一定集中在左边，不可行点集中在右边，中间是一条清晰的分界线。

于是"求最大的可行 H"就等价于"找到这条分界线左侧的最后一个点"。这正是整数二分最擅长的活。二分的思想是：每次取当前区间的中点 mid，判断它可行不可行，然后根据结果砍掉一半区间。可行就把左边界推到 mid，不可行就把右边界收到 mid 左边。每轮区间长度至少减半，log 级别轮数就能锁定答案。

拿具体数字感受一下：树高上界 10^9，二分只需要约 30 轮。每轮扫一遍 N 棵树，N = 10^5 时总运算量约 3×10^6，和之前的 10^14 比起来，等于把一条走不完的路缩成了一步。这就是单调性带来的红利。

2.3 上下界怎么取：从 f(0) 和 f(maxH) 说起

二分要有一个起点区间，而我习惯把左边界定在 0，右边界定在所有树高的最大值 maxH。这不是随手定的，每一步都有理由。

先看左边界。取 H = 0，意味着贴着地面锯，木材量 f(0) = Σ h_i，这是所有可能取到的最大值。如果连这个值都小于 M，那说明无论怎么锯都凑不够，题目无解。正常题目会保证 Σ h_i ≥ M，否则答案不存在，这属于出题人该管的边界。把左边界设成 0，实际上是把"理论最大收获"作为可行性兜底。有些版本树高最低是 1，那把左边界设成 1 也行，反正 0 到 1 之间不会有别的整数点。

再看右边界。取 H = maxH，木材量 f(maxH) = 0，一定不满足条件（除非 M = 0，这个特殊情况后面单独说）。所以答案一定落在 [0, maxH - 1] 这个范围内。把右边界设在 maxH 是安全的，多余那一个点会在二分过程中被自然淘汰。

这里有个实际的小技巧：读入树高的同时就顺手维护 maxH，不要读完之后再单独扫一遍 max。省一次遍历，虽然对复杂度没影响，但代码更紧凑，也不容易忘。

3. 整数二分写法里的三个致命细节

3.1 mid 取上整还是下整，决定了你会不会死循环

整数二分最坑人的地方不是思路，而是写法。思路谁都会，但模板选错，程序要么死循环要么答案差一。核心问题出在 mid 的取整方式上。

看这段代码：

while (l < r) { ll mid = (l + r) / 2; // 下取整 if (check(mid)) l = mid; // 注意这里是把 l 推到 mid else r = mid - 1; }

当 l 和 r 相差 1 的时候，mid = (l + r) / 2 = l。如果 check(mid) 为真，l = mid = l，区间一点没变，下一轮还是同样的状态，程序就永远卡在这里了。这就是经典的死循环。

修法是把 mid 改成上取整：

ll mid = l + (r - l + 1) / 2;

同样 l 和 r 相差 1，mid = l + 1 = r，此时无论 check 结果如何，区间都会缩小：真则 l = r，假则 r = l，循环退出。

规律很好记：只要你的更新分支里有l = mid，mid 就必须上取整；反之如果分支里是r = mid，mid 就下取整。这条规律我写在便签纸上贴了好几年，因为每次隔一阵子不写二分，就会忘。

顺便说一句，l + (r - l + 1) / 2这种写法比(l + r + 1) / 2更稳妥，原因下一节讲。

3.2 check 的分支挂在哪一边：单调递减时的判断翻转

另一个高频错误是判断分支写反。因为这道题的 f(H) 是单调不增的，所以"可行"对应的是较小的高度，而不是较大的高度。写代码时脑子里要清楚：f(mid) >= M成立，说明 mid 这个高度是可行的，而我们要的是最大可行高度，所以答案至少是 mid，于是l = mid；不成立说明 mid 太高了，答案在 mid 左边，于是r = mid - 1。

如果题目变成"求最小可行高度"（比如 f(H) 单调递增的情形），分支就得整体翻转，l和r的更新互换。很多人做题时明明单调性搞对了，代码却写反，就是因为把"递增型二分"的肌肉记忆直接搬了过来。

我的习惯是写代码前先在纸上画一行格子，标出哪边可行哪边不可行，然后把l = mid和r = mid - 1分别写在对应的格子上，再动手敲。这个动作只花十几秒，能省下半小时的调试。

3.3 左右边界的开闭：我的固定习惯与理由

二分模板五花八门，有闭区间[l, r]、左闭右开[l, r)、还有把答案变量单独拎出来更新的写法。我的建议是：固定一套自己最熟的，别来回换。

我自己固定用闭区间配"可行区间收缩"的写法，也就是初始l = 0, r = maxH，循环条件l < r，mid 上取整，可行就l = mid，不可行就r = mid - 1，最后输出l。这套写法的好处是循环结束时l == r且这个点一定是可行区间的右端点，也就是答案，不需要额外的变量记录，也不需要在循环外做任何判断。

另一套常见写法是维护ans变量，每次 check 成功就ans = mid，然后正常收缩区间，最后输出ans。这套也不容易错，尤其在单调方向复杂的时候更直观，代价是多一个变量。两种都行，但你得选定一种练到闭眼能写。

注意：这张表里两种写法的 mid 取整方式不同，千万别混着用。收缩型的可行分支是l = mid，必须上取整；记录型的可行分支是l = mid + 1，下取整即可。混用是死循环的常见来源。

4. 数据类型与边界：实测中最容易翻车的两类输入

4.1 累加和溢出：1e6 棵树乘 1e9 的高度意味着什么

这道题的数据范围里藏着第一个大坑：溢出。假设 N 最大 10^6，树高最大 10^9，那么 f(0) = Σ h_i 的最大值就是 10^15 量级。而 32 位有符号整数（C++ 里的int）上限约 2.14×10^9，差了六个数量级。

这意味着什么？假设你用int存累加和，程序不会报错，只会安静地给你一个错的答案。因为整数溢出在 C++ 里是未定义行为，实际表现往往是高位被截断，结果变成一个莫名其妙的小数甚至负数。你的二分逻辑完全正确，但答案是错的，而且这种错很难从输出上看出来——它不会崩溃，只会静静地骗你。

修法很直接：所有跟"木材总量"相关的变量统统用 64 位整数，C++ 里是long long，Java 里是long，Python 天然支持大整数所以不用管。特别注意三处：树的数组、check 函数里的累加变量、二分的左右边界。数组用long long看起来有点浪费内存，但只要树的棵数不超过 10^6，也就是 8MB 左右，完全在合理范围内，不要为了省这点内存去踩坑。

Python 这边反过来的问题不是溢出而是慢，后面单独说。

4.2 空集与全切：当 M 大于总木材量、或小于最小差值

边界情况里最需要单独拎出来说的是 M 的极端取值。

如果 M 大于所有树高加起来的总和，那么无论锯片设成 0 还是其他任何值，都凑不出这么多木材，题目无解。正常情况下出题人会保证有解，但你自己写题解或者写通用代码时，心里要有这个前提。如果真要处理，可以在读入时顺便算一下总高度，小于 M 就输出一个约定的无解标记。

如果 M 等于 0，那就是另一个极端。因为 f(maxH) = 0 ≥ 0 成立，所以 maxH 本身就是一个可行解，而它又是所有候选高度的上界，答案就是 maxH。这就是"锯片设得和最高的树一样高，一根木头都不砍"的情况。二分程序如果写得对，会自动得出这个结论：每轮 check 都成立，l一路推到r，最后输出 maxH。

还有一种隐蔽情况是"恰好等于 M"。伐木工这题的常见版本用的是"不少于 M"，因为 f 是阶梯函数，很可能某个值根本取不到精确的 M，用"不少于"能保证答案存在。如果你遇到的是"恰好 M"的版本，就得额外讨论 f 的跳跃点，解题难度会上升一个档次，通常不会出现在基础题里。

4.3 树高分布极不均匀时的表现

最后一类容易出问题的输入是树高分布极其悬殊的情况，比如一棵树高 10^9，其余 10^5 棵树都只有 1。

这时候还要不要用二分？要。二分的轮数取决于高度的取值范围，也就是 log(maxH)，跟你砍掉多少棵树无关，三十轮还是三十轮。但每轮 check 的代价是固定的 O(N)，因为函数里那个if (h[i] > mid)判断每棵树都要走一遍，哪怕绝大多数树根本够不着。

这种"分布悬殊"的输入在随机数据里很常见，也是很多人在本地测都过、提交就超时的原因——随机数据下二分的轮数偏多。想优化的话，就是后面第 6 节讲的排序加前缀和，把每轮 check 从 O(N) 压到 O(log N)。不过对基础题来说，直接用朴素二分通常就够了。

5. 两版可运行的实现与对拍验证

5.1 C++ 参考代码与逐行说明

先给出一版我平时直接用的实现，闭区间收缩型，全程 64 位整数：

#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; const int MAXN = 1000005; int n; ll m; ll h[MAXN]; // 锯片高度为 x 时，能得到的木材总量 ll cut(ll x) { ll total = 0; for (int i = 0; i < n; ++i) { if (h[i] > x) total += h[i] - x; } return total; } int main() { scanf("%d %lld", &n, &m); ll hi = 0; for (int i = 0; i < n; ++i) { scanf("%lld", &h[i]); if (h[i] > hi) hi = h[i]; // 顺带维护树高上界 } ll l = 0, r = hi; while (l < r) { ll mid = l + (r - l + 1) / 2; // 上取整，防止死循环 if (cut(mid) >= m) { l = mid; // mid 可行，答案不小于 mid } else { r = mid - 1; // mid 太高，往左收 } } printf("%lld\n", l); return 0; }

逐行看几个关键点。cut函数只做一件事，就是把木材总量算出来，不掺杂任何二分逻辑，这样职责单一，也方便后面单独测试。hi在读入时顺带维护，省一次遍历。mid用l + (r - l + 1) / 2而不是(l + r + 1) / 2，是为了避免l + r本身溢出——虽然在这道题里l、r都只有 10^9 级别，加起来不会溢出，但养成这个习惯没坏处，遇到边界到 10^18 的题目就能救命。最后输出l，因为循环结束时l就是最大的可行高度。

5.2 Python 版本，以及它在 1e6 数据下的表现

Python 写起来短很多，但性能是个真问题：

import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) m = int(data[1]) h = list(map(int, data[2:2 + n])) lo, hi = 0, max(h) while lo < hi: mid = (lo + hi + 1) // 2 total = 0 for x in h: if x > mid: total += x - mid if total >= m: lo = mid else: hi = mid - 1 print(lo) main()

用sys.stdin.buffer.read()一次性读入再切分，比逐行input()快得多，这是 Python 刷题的基本功。但即便如此，当 N = 10^6、二分 30 轮时，内层循环要执行约 3×10^7 次，纯 Python 的这个量级大概要十几秒，很可能超时。

我实测过几种优化路线。用 numpy 做向量化能把内层循环压到毫秒级，但每次 check 都要新建数组、做减法再clip求和，内存和构造开销不小，属于能用但不优雅。真正稳妥的做法是排序加前缀和，把每轮 check 变成一次bisect加一次乘法，复杂度从 O(N log maxH) 降到 O(N log N + log maxH · log N)，主要开销落在排序上，Python 的sort是 C 实现的，10^6 个数大概一秒内能搞定。这个方案下一节展开。

5.3 用暴力程序对拍：我常用的验证流程

二分写完之后，我的第一反应从来不是直接提交，而是写一个暴力程序对拍。原因很简单：二分的错误多半是边界和取整，靠眼看来回检查效率太低，让机器帮你找反而快。

暴力程序思路是枚举所有可能的 H，算出 f(H)，从大到小找第一个满足条件的：

import random def brute(n, m, h): for H in range(max(h), -1, -1): if sum(x - H for x in h if x > H) >= m: return H return -1

然后写个生成器造小数据：N 取 1 到 20，树高取 1 到 50，M 取 1 到 sum(h)，循环几千组，把两个程序的输出逐一比对。这个流程跑一次也就几秒钟，但能覆盖掉绝大多数的取整和边界错误。我用这套方法抓到过好几次"l 和 r 相邻时结果差一"的问题，那种错误如果靠提交看反馈，一次就要等半天。

提示：对拍的小数据一定要覆盖 M = sum(h)、M = 0、所有树高相同、只有一棵树、N = 1 且 M 很小这几种极端情况。随机均匀数据反而抓不到边界 bug。

6. 排序加前缀和：当询问不止一次时的另一种解法

6.1 把 check 从 O(N) 降到 O(log N) 的思路

朴素二分每次算 f(H) 都要扫全数组，这在线性调用的场景下是必要开销。但当 N 很大、又想多跑几轮二分时，每次 O(N) 就成了瓶颈。观察一下 f(H) 的表达式：

f(H) = Σ (h_i - H)，对满足 h_i > H 的那些 i

这个求和可以拆开：设满足条件的树有 k 棵，那么 f(H) = (这些树的高度之和) - k × H。如果我能快速求出"所有大于 H 的树的高度之和"以及"这些树的棵数"，f(H) 就能在 O(log N) 内算出来。而这两个量，正好可以用排序加后缀和预处理。

6.2 前缀和的构造与差值的精确计算

具体做法：先把树高数组从小到大排序，记排序后的数组为 a[0..n-1]，再构造后缀和 suf[i] = a[i] + a[i+1] + ... + a[n-1]，其中 suf[n] = 0。

对于给定的 H，用二分查找找出第一个大于等于 H 的位置 p，也就是p = lower_bound(a, H)。因为数组有序，所有下标 i ≥ p 的树都满足 a[i] ≥ H，贡献为 a[i] - H；下标小于 p 的树贡献为 0。

于是：

f(H) = suf[p] - H × (n - p)

这里有个细节要留意：lower_bound找的是第一个大于等于 H 的位置，而 a[i] = H 的树贡献恰好为 0，包含进来也不影响结果，所以用lower_bound是完全正确的。如果手滑用了upper_bound（第一个大于 H 的位置），结果的数值其实也一样，但含义上差了一点——等于 H 的树被排除了，贡献本来也是 0，所以数值不受影响。不过我还是习惯用lower_bound，因为它的定义跟"哪些树会被切"更贴合，读代码的人一眼就能明白。

还要处理 p = n 的情况，也就是 H 大于等于所有树高，此时 suf[n] = 0，n - p = 0，f(H) = 0，公式依然成立，不需要额外特判。这也是后缀和写法比在 C++ 里手动管理数组边界舒服的地方。

6.3 什么时候值得上这套优化

这套优化值不值得上，取决于三个因素。

第一是 N 的大小。N 在 10^5 以下时，朴素二分的总运算量也就 3×10^6 左右，C++ 里几乎瞬间完成，没必要增加代码复杂度。N 到 10^6 时差距开始显现，但朴素版通常还能过。N 到 10^7 级别，朴素版就危险了。

第二是语言。如果题目必须用 Python 提交，那我建议不管 N 多大都直接上排序加前缀和，因为 Python 的循环实在太慢，这几乎是唯一能在合理时间内跑完的方案。

第三是询问次数。如果题目在基础版之上变成"给你 Q 个不同的 M，每个都要一个答案"，那排序加前缀和的优势会被放大 Q 倍。这种情况下朴素二分的总复杂度是 O(Q · N · log maxH)，而优化版是 O(N log N + Q · log maxH · log N)，差距非常明显。

7. 认出二分答案的三类信号

7.1 信号一：答案是一个可以比较大小的数值

二分答案的适用前提里，有一条最容易被忽略：答案本身必须是一个数值，而且能比较大小。伐木工这题求的是锯片高度，是整数，天然可比。反过来说，如果一道题要求输出一组具体的方案（比如"砍哪几棵树"），那二分答案就不直接适用，得换个思路。

更普遍地说，凡是"求最大值""求最小值""求第 k 大""求最小的最大"这类题型，答案都是一个数值，都值得先考虑二分答案。这也是为什么二分的题目描述里经常出现"尽可能大""最小化最大值"这样的字眼——它们几乎就是路标。

7.2 信号二：存在一条"满足/不满足"的分界线

第二个信号是存在一条清晰的分界线，分界线的一边满足某个条件，另一边不满足，并且随着候选值单调移动，这个条件的状态只会翻转一次，不会来回横跳。

这道题里，分界线就是"能否凑够 M 米木材"。高度低的时候能凑够，高度高的时候凑不够，中间只翻转一次。如果条件的状态在取值范围内来回变化，比如"高度低时不够，中间够，再高又不够"，那就没法用二分，因为中点处的信息无法帮你排除任何一半。

判断这一点的方法就是上一节做的单调性证明：写清楚函数表达式，看看它关于自变量是不是单调的。能证出来，二分就成立；证不出来，就得换算法。

7.3 信号三：直接求答案难，但验证答案容易

第三个信号最实用：直接构造答案很难，但给定一个候选答案去验证它是否可行却很容易。

让我从零开始构造一个最大的锯片高度，这件事本身没什么好办法，只能试。但如果你告诉我"锯片设在 H，行不行"，我扫一遍树就能立刻回答，这就是 check 函数 O(N) 的由来。二分答案的整套结构就是围绕这个不对称性设计的：把"求最优解"这个难问题，转化成 log 次"验证某个解"的简单问题。

这套思路的适用范围远不止伐木工。木材切割、绳子分段、包裹装箱、整数开方、找旋转数组的拐点、乃至某些动态规划里的"可行性判定"，都能套这个框架。当你把"求答案"和"验答案"的难度对比一下，发现后者明显更简单，那基本就可以确定这是一道二分答案题了。

我自己刷题时养成了一个习惯：拿到题目先不看标签，直接问自己这三个问题——答案是不是一个数？条件是不是单调的？验证是不是比求解简单？三个都是"是"，那九成就是二分答案，接下来无非是写 check 函数和调边界。这三个问题花不了两分钟，但能帮你在一堆陌生题面里快速锁定方向，省下的时间够你多刷两道题。至于具体的边界该取 0 还是 1、M 该不该用 64 位，这些细节还是老老实实对拍一遍比较踏实，因为我在这些地方栽过的跟头，实在比思路上的错误多得多。