题库里编号 1908 的这道《伐木工》，标签上就俩字——基础。但我见过太多人在这道"基础题"上栽跟头：要么二分写成了死循环，交上去一直是那个刺眼的红字；要么判定函数里用了 int，被一组几十万棵树、每棵高上亿的数据直接干翻。它之所以被放在基础区，不是因为简单，而是因为它把二分答案这套方法的每一个坑都摆在了最显眼的位置上。把这道题吃透，你后面遇到的"最大值最小""最小值最大"类问题，基本都能靠同一套肌肉记忆解决。下面我就按自己平时解题和讲课的顺序，从建模、选型、边界、代码、对拍到变式，完整地拆一遍。适合刚学二分的新手，也适合想回头查漏补缺的老手。

1. 题目模型拆解与算法选型思路

1.1 把砍树这件事翻译成一句数学命题

先把题面用大白话还原一遍：场上立着 n 棵树，第 i 棵树的高度是 h_i。伐木工把锯子水平架在某个高度 H 上，凡是比 H 高的树，高于 H 的那一截被整体切下来变成木材，长度就是 h_i 减去 H；凡是本身就不超过 H 的树，一根木头都产不出来。现在要求这些木材的总长度加起来不少于 m，问这个 H 最大能架多高。

转成数学语言就是：求满足 Σ max(0, h_i − H) ≥ m 的最大的整数 H。这一步转译是整个解题过程里最关键的一步，很多人写不出来不是不会二分，而是没把中文题面精确地翻译成含绝对值或者取最大值的式子。我个人的经验是，读题之后一定先强迫自己写出这条不等式，写在草稿纸最上面，后面所有的边界讨论都围绕它展开。

生活里有个特别贴切的类比：这就像往一个不规则的容器里舀水，水位线压得越低，能舀出来的水越多；水位线抬得越高，舀出来的水越少。H 就是那条水位线，"产出木材总量"关于 H 是严格递减的关系，我们要找的就是"刚好还够舀出 m 这么多水"的那条最高水位线。

1.2 为什么第一反应不该是从高往低枚举

最朴素的思路非常诱人：H 从最高的树开始，每次减一，算一遍总产出，第一个满足条件的就是答案。思路没错，复杂度也一目了然——枚举次数最多是 max(h) 次，每次判定要扫一遍 n 棵树，总复杂度 O(n · max h)。

问题出在数据规模上。当 n 只有 1000、树高不超过 1000 的时候，这个暴力是 10^6 量级，随便跑；可一旦 n 涨到 10^5、树高上限到 10^9，暴力就是 10^14 次基本操作，别说一秒，给你一小时都跑不完。这时候必须换思路。

我教新人的时候常说一句话：只要你在题目里看到"最大/最小"配上"满足某个数量条件"，而且那个条件的可行性是单调的，那九成九是二分答案。这道题就是最标准的模板，连变形的余地都没有。

1.3 单调性证明：二分答案真正的通行证

很多人用二分答案是"背模板"，问他为什么能二分，答不上来。这道基础题恰好是练证明的好材料，证明只有一行：

假设高度 H 是可行的，那么对任意 H′ < H，因为 h_i − H′ ≥ h_i − H 对每一棵树都成立，所以 H′ 处的总产出 ≥ H 处的总产出 ≥ m，也就是说 H′ 必然也可行。

这句话翻译过来就是：可行的高度集合一定是一个从 0 开始的连续前缀区间 [0, H*]，不存在"中间可行、两边不可行"这种坑爹形态。有一侧单调，就能二分，这是二分答案能成立的全部地基。

提示：二分答案的前提从来不是"题目看起来像二分"，而是"判定函数关于答案具有单调性"。写完代码前先在草稿纸上把这段证明写出来，比事后对拍一百组数据都管用。

1.4 判定函数：把优化问题降级成判断题

二分答案的通用套路是"把求最优值转成判定是否可行"。这道题里，check(H) 的任务非常干净：给定一个高度 H，算一算总产出够不够 m，返回 true 或者 false。原本让人头疼的"最大化 H"问题，被拆成了大约三十次"够不够"的是非题。

这个思路的价值在于降维。找出最大值往往需要巧思，而判断"某个给定方案是否达标"通常只需要老老实实累加一遍。整个算法的骨头就是两根：一根是有序的搜索空间，一根是廉价的判定函数。判定函数写得越干净，二分部分就越不容易出错。

2. 边界、判定与整数二分的实操细节

2.1 上下界怎么取，直接决定迭代次数和溢出风险

搜索区间我一般取 lo = 0，hi = max(h)。lo 取 0 是有讲究的：如果题目数据保证有解，答案最小就是 0，也就是把锯子架在地面上，所有树全砍，这是理论上的产出上限。lo 取 0 而不是取 1，是为了让"树高很矮、m 很小的数据"不会漏掉正确答案 0——虽然多数版本保证 m ≤ 总产出，但边界留一手总没坏处。

hi 取 max(h) 而不是取一个大到离谱的常数（比如 10^9），理由有两个。第一，锯子架得比最高的树还高，产出必定是 0，那些区间全是无效迭代，白白多跑几次判定；第二，hi 取得过大，某些写法里的 mid 计算虽然不会溢出，但会让"答案恰好等于 max(h)"这种边界情况下的收敛过程变得难以推理。

提示：能精确取到的上界一定要精确取，别偷懒写成 1e9。二分题的 hi 定错，等价于给答案挖了一个自己看不见的坑。

2.2 check 函数里三个容易被忽略的写法要点

第一是提前退出。判定函数没必要把所有树都累加完，一旦累加值已经大等于 m，立刻 return true。别小看这一句剪枝，在实际数据里，如果 m 很小而树很多，它能省下大量加法。

第二是累加变量必须用 64 位整数。n 最大到 10^5、h_i 最大到 10^9 的时候，总产出上限是 10^14，早就超出了 32 位整数大约 2.1×10^9 的表达能力。老实说，我自己在训练初期就在这类"加一加就溢出"的题上吃过不下五次的罚，后来养成的习惯是：只要题目里出现"累加"，变量一律用 long long，不纠结。

第三是别做无意义的取模或开方。有些同学喜欢在判定里用 sqrt 或者对数提前估个大概，二分题里完全不需要，浮点误差反而会把边界搞乱。整数题就用整数算，干净利落。

2.3 整数二分的三种常见模板与死循环陷阱

整数二分的写法五花八门，但坑其实只有一个：mid 的取整方向和边界的收缩方向必须配套，否则要么死循环，要么答案差一。下面把我常用的三种写法列出来对比。

新手我强烈推荐第一种"记录答案法"。它的好处是心理负担极低：只要 ok(mid) 成立，就把 mid 记下来，然后往更大的方向试；不成立就往更小的方向试。区间一定会收缩（因为两边都是 mid±1），根本不可能死循环。代价只是多一个变量和一次赋值，换来的是五分钟就能写完并且一次过。

第二种写法是很多模板文里的默认写法，它的效率略微高一点点，但mid = (lo + hi + 1) / 2那个加一是命门。如果写成mid = (lo + hi) / 2，在 lo 和 hi 相邻时 mid 会等于 lo，而 ok 成立时lo = mid又不动，于是原地转圈，程序永远停不下来。这类死循环不会报错，只会让你在提交页面上看到 TLE，然后一头雾水地盯半天代码。

2.4 一个常被忽略的边界：全都砍不到怎么办

有一种边界情况值得单独说：当把所有树全部砍倒（H = 0）的总产出都小于 m 时，判定函数在整个搜索区间上都返回 false。这时候"记录答案法"里的 ans 会保持初始值，输出 0。这个结果在数学上是"无解"，但在很多题面里会被保证不会出现。我建议的稳妥做法是：先读入的时候顺手把总高度加起来，如果总高度小于 m，按题目要求处理——要么输出 0，要么特殊判断。多写这三行，能防住一整类神秘的错误答案。

3. 代码实现与完整实操流程

3.1 C++ 版本：一份可以直接抄的模板

下面这份代码是我平时训练时用的版本，读入用ios::sync_with_stdio(false)关同步，累加用 long long，二分用记录答案法，基本可以直接套到任何"最大值可行"的二分题上。

#include <bits/stdc++.h> using namespace std; int n; long long m; vector<long long> h; bool ok(long long H) { long long sum = 0; for (int i = 0; i < n; ++i) { if (h[i] > H) { sum += h[i] - H; if (sum >= m) return true; // 提前剪枝，够用就走 } } return sum >= m; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); if (!(cin >> n >> m)) return 0; h.resize(n); long long mx = 0, total = 0; for (int i = 0; i < n; ++i) { cin >> h[i]; mx = max(mx, h[i]); total += h[i]; } if (total < m) { // 全砍完都不够，按题目要求处理 cout << 0 << '\n'; return 0; } long long lo = 0, hi = mx, ans = 0; while (lo <= hi) { long long mid = lo + (hi - lo) / 2; // 防溢出写法 if (ok(mid)) { ans = mid; lo = mid + 1; // 试试更高的锯位 } else { hi = mid - 1; // 架太高了，降下来 } } cout << ans << '\n'; return 0; }

几个细节解释一下。mid = lo + (hi - lo) / 2和(lo + hi) / 2在 long long 范围内其实差不多，但前者是更保险的写法，两个大数相加不会溢出，是个值得养成的习惯。total在输入阶段顺带统计，用来做无解判断，几乎零成本。提前剪枝那句if (sum >= m) return true;放在循环内部而不是循环外，是因为一旦够了就没必要继续扫，在 m 偏小的数据上能明显提速。

3.2 Python 版本：排序加前缀和把判定压到 O(log n)

Python 写这题要留个心眼：如果判定函数是 O(n) 的线性扫描，n = 10^5、二分大约 30 轮，就是 3×10^6 次加法，用纯 Python 循环跑通常能过但要一两秒，碰上更狠的数据就悬了。我的做法是提前排序并做前缀和，把每次判定降到 O(log n)。

import sys from bisect import bisect_right def main(): data = sys.stdin.buffer.read().split() n, m = int(data[0]), int(data[1]) h = list(map(int, data[2:2 + n])) h.sort() pre = [0] * (n + 1) for i in range(n): pre[i + 1] = pre[i] + h[i] def ok(H): k = bisect_right(h, H) # 高度 <= H 的树有 k 棵，一棵都出不了木材 total = (pre[n] - pre[k]) - (n - k) * H return total >= m if pre[n] < m: print(0) return lo, hi, ans = 0, h[-1], 0 while lo <= hi: mid = (lo + hi) // 2 if ok(mid): ans = mid lo = mid + 1 else: hi = mid - 1 print(ans) sys.stdout.write(str(ans) + "\n") main()

这段的核心在于那条公式：所有高于 H 的树贡献的总和，等于"所有树高度之和"减去"高度不超过 H 的那些树的高度之和"，再减去"高于 H 的树的数量乘以 H"。前半部分用前缀和 O(1) 拿到，树的数量用二分查找 bisect_right 在 O(log n) 内定位。整道题的总复杂度变成 O(n log n + log(max h) × log n)，在 Python 里基本是毫秒级的事情。

3.3 复杂度账：数据规模对照表

我一直觉得，写题时不先把复杂度账算清楚，等于闭着眼睛开车。下面这张表把暴力枚举和二分答案在几档典型规模下的运算量摆在一起，差距一眼可见。

这里的 log 底数是 2，因为每次判定把区间砍一半。log₂(10^9) 大约是 30，也就是说二分的迭代次数永远在 30 上下，几乎和数据范围无关。这就是二分答案最迷人的地方：搜索空间的绝对大小不重要，重要的是它的对数规模。

3.4 一次完整的实操流程记录

我在本地做这道题的习惯流程是这样，顺序基本固定，几乎不会漏东西。第一步，读题并在纸上写下不等式 Σ max(0, h_i − H) ≥ m；第二步，验证单调性，写一句话证明；第三步，定上下界，lo = 0，hi = max(h)；第四步，先写判定函数并用手算样例验证；第五步，套二分模板；第六步，造三组数据：树高全相等、只有一棵树、m 恰好等于总产出的一半，跑一遍看结果合不合理；第七步，写暴力对拍。

这个顺序的意义在于把"设计"和"编码"分开。很多人一上来就敲代码，结果边界错、方向反、溢出，全混在一起，调起来极其痛苦。先把不等式和单调性写在纸上，等于给自己画了张地图，后面出问题也能快速定位到底是哪一步错了。

4. 常见问题与排查实录

4.1 典型错因速查表

这是我这些年收集的、也是给学弟学妹讲得最多的一张表。同一个错误反复出现，说明它不是偶然，而是思维上的惯性漏洞。

表格里最值得说的是第一条。死循环是二分题的头号杀手，而且它不给你任何提示，只会让你对着屏幕发呆。我的判断办法很简单：只要代码里出现了lo = mid这种"赋值不推进"的语句，立刻条件反射地去检查 mid 的取整是不是向上取整。

4.2 对拍：让暴力程序给二分当裁判

对拍是排查二分边界问题最有效的武器，没有之一。原理很朴素：写一个一定正确的暴力程序，再写一个随机数据生成器，循环跑几百组，比对两个程序的输出。只要有一组不一样，就把那组数据留下来手工分析。下面是 Python 的简易对拍脚本。

import random, subprocess def brute(n, m, h): # 从高到低枚举锯位，第一个满足条件的就是答案 total_all = sum(h) if total_all < m: return 0 for H in range(max(h), -1, -1): if sum(x - H for x in h if x > H) >= m: return H return 0 for t in range(1, 501): n = random.randint(1, 8) h = [random.randint(1, 20) for _ in range(n)] m = random.randint(1, sum(h)) # 保证有解，先把核心逻辑跑通 inp = f"{n} {m}\n{' '.join(map(str, h))}\n" out1 = subprocess.run(["./sol"], input=inp, capture_output=True, text=True).stdout.strip() out2 = str(brute(n, m, h)) if out1 != out2: print("发现问题数据：") print(inp) print("二分输出：", out1, " 暴力输出：", out2) break else: print("500 组全部一致")

跑对拍时有三个细节要注意。第一，先用小数据（n ≤ 8、h ≤ 20）跑，这样万一出错，你能手工验算；第二，m 的取值范围一定要先限定成"必定有解"，把核心逻辑确认无误之后，再放开边界去测试无解的情况；第三，随机数的种子最好固定一下，方便复现，不然偶发的错误数据丢了，你得重新碰运气。

4.3 手推一组样例，把抽象过程具象化

看代码之前，先手推一组数据，理解会牢固得多。设四棵树高度分别是 20、15、10、17，要求总木材不少于 7。

H = 15 的时候，产出是 (20−15) + (17−15) = 5 + 2 = 7，刚好够。H = 16 的时候，产出是 4 + 1 = 5，不够。所以答案是 15。

这组数据有意思的地方在于它正好卡在边界上，7 这个数字不偏不倚。我建议每个人在自己做题的时候都准备两组这种"刚好卡住"的样例，因为它能同时验证两件事：可行值能取到，且不可行值确实被排除了。如果你的代码对 H = 15 输出 14 或者 16，那基本可以确定是边界收缩写错了，直接去看模板那一节。

4.4 读入和常数优化上的小经验

最后分享几个实战里总结的小经验，都是正规题解里很少写、但能实实在在省下提交次数的东西。

第一，输入量大的时候一定要关同步或者用快读。C++ 里ios::sync_with_stdio(false); cin.tie(nullptr);这两行我几乎是条件反射地写上，它带来的提升在大数据下非常明显。Python 里则要用sys.stdin.buffer.read().split()一次性读完，而不是一行一行input()。

第二，判定函数里的剪枝要放在循环体内。很多同学把提前退出写在累加完成之后，等于白写。真正有效的剪枝是在累加的过程中一旦达标立刻返回。

第三，不要迷信"基础题"这三个字。这道题的每一个知识点都不难，但知识点多，任何一环出错都会导致整体失败。把每个环节都在纸上写清楚，比反复重写代码高效得多。

5. 变式与进阶拓展

5.1 "恰好等于"版本的改法

如果题面把条件改成"总产出恰好等于 m"，思路稍微变一下。做法是先用同样的二分找出满足总产出 ≥ m 的最大 H，记为 H*，然后单独算一次 check(H*) 对应的实际总产出，如果它正好等于 m，就输出 H*；如果大于 m，说明无论如何都凑不出恰好等于，按题面要求输出无解标识。

这里有个思维上的提醒：二分能处理的永远是"不等式"形式的单调判定，"恰好等于"这类等式约束需要在不等式结果的基础上再补一次校验。把这两件事混在一起写进判定函数，是新手很容易掉进去的坑，因为"恰好等于"关于 H 并不单调，根本没法二分。

5.2 换个外壳：切木头与合并木头

同一个算法核心，换一层题面就能变成另一道题。比如把"砍树"换成"把若干根原木切成等长的 k 段，求每段的最大长度"，判定逻辑一模一样：给定长度 L，算一算所有原木能切出多少段，够不够 k。再比如把问题反过来，要求"把若干段木料合并成规定的段数，使总代价最小"，那就不是二分答案了，而是经典的优先队列贪心，每次取出最短的两段合并。

我经常拿这一组题放在一起讲，目的就是让读者意识到：题面是皮，模型是骨。看到"砍"和"切"，先问自己一句——这是可行性单调的判定问题，还是每一步都要做局部最优决策的贪心问题？分清楚这两类，选型就不会跑偏。

5.3 多工人并行版本的一点思路

还有一种常见变形：场上不止一个伐木工，每人只能在一个固定高度切一刀，问怎么安排高度使得总产出达标。这种题通常就不是单纯的二分答案了，需要先排序再贪心分配，或者转成"二分答案加可行性贪心检查"的组合。

组合类题目我个人的经验是：先别急着上算法，先把题目里的约束一条条列出来，看清楚哪一条是单调的、哪一条是组合性的。单调的那部分用二分处理，组合的那部分用排序或堆处理，两者拼起来往往就是标算。硬套单一模板，十有八九会在某组数据上翻车。

5.4 从这道题沉淀下来的通用套路

最后说点方法论层面的东西。这道题教会我的东西，其实远远超出"会写二分"这个层面。

第一，遇到"最大值最小""最小值最大""满足条件的最优值"，先写判定函数，再想二分，这个顺序不能反。判定函数写清楚了，二分只是壳子。

第二，单调性一定要证明，哪怕只是一句话。没有单调性支撑的二分就是空中楼阁，对拍再多次也救不了。

第三，边界永远是最贵的地方。上下界的选取、mid 的取整方向、循环终止条件，这三处我每次都会多看两眼。经验告诉我，绝大多数二分 WA 都死在这三处，而不是死在算法思想上。

第四也是最实在的一条：所有涉及累加的变量，先用最宽的整数类型，等到确认性能有问题再考虑降位。省下来的那点内存，根本抵不上一遍遍调试溢出的时间成本。这个习惯我从这道基础题开始养成，后来打各类比赛时救过我好几次。

顺便提一句，这道题如果数据范围不大，用排序加双指针甚至可以直接算出答案，但那就失去练习二分的意义了。既然是拿它当练手题，就老老实实按二分答案的完整流程走一遍，把判定函数、边界、对拍这三样东西完整地过一遍手。以后再遇到同类问题，你会发现自己的第一反应已经变成"先看单调性"，而不是"先想暴力怎么优化"。