你看到“砍树”这道二分答案题，第一反应是不是“这有什么好讲的，不就是套个二分模板”？但说真的，我见过太多人在 P1873 上栽跟头——有二分边界写错的，有死循环跳不出来的，有样例过了结果 WA 到怀疑人生的。问题不在于你知不知道二分，而在于你对“二分答案”这个套路有没有形成肌肉记忆。今天我就拿这道洛谷 P1873 砍树题当靶子，把二分答案从思路到代码、从边界到调试，完整拆一遍。这篇文章适合刚学完二分查找、准备进阶二分答案的初学者，也适合想系统梳理套路的中学生竞赛选手，当然你如果是大学生期末复习数据结构，看到这篇也能少走不少弯路。

1. 题目到底在说什么：先读懂砍树的数学模型

1.1 从一个生活场景说起

伐木工人米尔科有一台锯木机，他可以把锯子的高度设成一个整数 H，机器从左到右扫过每一棵树，凡是高度大于 H 的树，高出 H 的那一截就会被锯下来，变成木材；如果树的高度本身小于等于 H，那这棵树就一根木头都贡献不出来。米尔科想要收集至少 M 米长的木材，但他同时又希望 H 设得越高越好——因为 H 越高，被砍到的树越少，森林看起来越“环保”，而且大部分情况下锯起来也省事。

题目会给你 N 棵树的实际高度，让你算出来这个最高能设到多少的 H。

这个场景转成数学语言其实特别简单：给你一个数组 a[1..N]，你需要找一个最大的整数 H，使得所有 a[i] 中大于 H 的部分“切下来”之和 >= M。切下来的量就是 max(0, a[i] - H)，对这 N 个数求和得到总木材量。

1.2 第一反应不能是暴力枚举

我第一次做这道题的时候，脑子里第一个蹦出来的想法是：那我把 H 从高往低一个一个试不就行了？每试一个 H，遍历一遍所有树，算一算总木材量够不够，够的话就直接输出。

这个思路完全正确，但它有一个致命问题：复杂度。假设树木高度的上限是 10^9，你从最高往下每次减 1，最多可能要枚举 10^9 次，每次又要遍历 N 棵树（N 最大也有 10^6），总操作量是 10^15 这个量级，在任何竞赛环境下都是直接超时。

现实生活里你也许不会觉得“从 10 亿往下数到某个数”有多久，但计算机面对这种数量级，运算次数轻松突破一秒限制的几百倍。所以这里必须换思路——不能一个一个试，要一批一批地淘汰。

1.3 二分答案本质上就是猜答案

二分查找大家都熟悉，在有序数组里找一个目标值，每次砍掉一半。二分答案是把这套“砍半”的逻辑用在了一个更高层的维度上：我们不是在一堆现成的数值里找一个存在的数，而是在一个可能的答案区间里，不断猜测“什么样的答案可行”。

放到砍树这道题里，答案 H 一定落在某个范围内，这个范围我们有明确认知：最低是 0（不砍任何树，当然木材为 0），最高不会超过所有树中的最大值 maxH。如果 H 取 0，肯定能满足 M（除非 M 是 0，但题目 M >= 1），如果 H 取 maxH，那所有树都砍不到东西，木材为 0，大概率不满足。所以真正的答案卡在 0 和 maxH 之间。

二分答案的精髓就是：取中间值 mid = (l + r) / 2，先假装 H = mid，检查一下这个高度下的木材总量够不够 M。如果够，说明 mid 这个高度是“可行”的，那答案至少是 mid，我们可以把区间左边界往上提；如果不够，说明 mid 太高了，砍不到足够的木头，那就把右边界往下降。每判断一次，可用的答案范围就缩小一半，从 0 到 10^9 的范围只需要大约 30 次判断，哪怕每次判断要扫描一遍 N=10^6 的数组，总计算量也就是 3000 万级别，轻松跑完。

2. 二分答案的套路拆解：为什么它能工作

2.1 单调性是整个二分的前提

很多人背下了二分模板，却不知道模板之所以能用的底层原因。二分答案能成立的根基，是“答案”和“可行性”之间存在单调关系。

在这道题里，单调性体现在：H 越低，能切下来的木材总量就越多；H 越高，木材总量就越少。换句话说，木材总量是随着 H 的增大而单调不增的函数。于是“是否满足木材 >= M”这个判断，在整个答案区间里呈现出一种特殊的性质——足够小的 H 都是可行的，足够大的 H 都是不可行的，中间存在一个分界线，分界线上的临界值就是我们要求的最大可行 H。

单调性保证了我们可以反复二分，因为每次判断完 mid 之后，一定能确定至少一半的区间里“所有值都可行”或者“所有值都不可行”，从而把范围安全地丢掉一半。如果题目缺少这种单调性，二分答案就不成立。

2.2 二分答案和二分查找的细微差别

普通二分查找是在一个“有序数组”里查某个确定的值，比较的是 a[mid] 和 target。二分答案则没有所谓的“目标值”可以直接比，它比较的是“用 mid 作为参数去执行一个判断函数（通常叫 check(mid)）”的返回值，判断的是 mid 这个候选答案是否满足约束条件。

所以二分答案的模板里，核心永远围绕三个问题：左边界 l 代表什么，右边界 r 代表什么，check(mid) 为真时应该缩小哪一边。很多初学者把跳转逻辑写反，根源正是因为脑子里还在想“找某个数”，而不是“判断可行”。

我建议你把二分答案直接理解成：维护一个包含所有可行答案的大区间，不断把区间中确定不可行的一半丢掉，最后收敛到边界值。变量 l 要么表示“当前已知的可行最大值”，要么表示“左开右闭区间中的开边界”，不同写法语义不同。

2.3 check 函数的编写思路

写二分答案题，最重要、也最需要细心的是 check 函数。它决定了每次二分迭代时的判断结果是否可靠。check 函数的逻辑在砍树这道题里就一行：遍历所有树，累加 max(0, a[i] - H)，如果累加结果大于等于 M，返回 true，否则返回 false。

这里有一个隐藏考点：累加值可能会非常大。N 最多 10^6，每棵树高度最大 10^9，当 H = 0 时总木材量可以达到 10^15。这个值远超 int 的表示范围，所以你在 check 函数里必须用 long long 类型累加，否则直接溢出变成负数，明明够的木材被判成不够，二分结果就偏了。

顺便说一句，有些人的 check 函数会“剪枝”：一旦累加值已经超过 M，就直接返回 true，不用继续遍历。这个优化在 N 特别大、M 比较小的时候收益明显，因为实在没必要把整片森林都扫完才知道够不够。代码上写起来就是循环里加一句 if (sum >= m) return true;。

3. 完整代码实现与关键细节

3.1 一份可以直接抄作业的 C++ 实现

先给结论，这个是我自己用着最顺手的写法，左闭右闭版本，不容易迷路：

#include <bits/stdc++.h> using namespace std; int n; long long m; long long a[1000005]; bool check(long long h) { long long sum = 0; for (int i = 0; i < n; i++) { if (a[i] > h) { sum += a[i] - h; if (sum >= m) return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; long long maxH = 0; for (int i = 0; i < n; i++) { cin >> a[i]; maxH = max(maxH, a[i]); } long long l = 0, r = maxH, ans = 0; while (l <= r) { long long mid = (l + r) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << endl; return 0; }

这段代码的核心逻辑一目了然：二分查找答案，check 判断 mid 是否可行。如果可行，记录当前 mid 作为候选答案，然后去更高的区间继续尝试；如果不可行，说明 mid 太高，只能往更低的区间找。

3.2 为什么初始区间设为 0 到 maxH

先说下界为什么是 0。题目里 H 是锯子的高度，H 只能是非负整数，低于 0 没有实际意义。而且 H 取 0 时所有高于 0 的树都会被完整砍倒，木材量肯定是最大值，一定满足 M >= 1 的要求，所以 0 一定可行。

再说上界为什么是 maxH。如果 H 大于等于森林中最高树的高度，那么没有任何树能贡献木材，sum 恒为 0，绝对不满足 M >= 1。所以答案不可能超过 maxH。把区间直接卡到 [0, maxH]，二分次数最多也就是 log2(10^9) 约 30 次，而且一开始就排除了大量无效区域。

有人问：上界设成 0 和 maxH，那会不会漏掉答案恰好是 maxH 的情况？不会，因为这棵树即使是最高那棵，只要 H = maxH，它自己刚好不高于 H，不存在“高于 H”的部分，所以确实砍不到木头。答案要想等于 maxH，必须 M = 0，但 M 至少是 1，所以答案必然小于 maxH。不过代码里用 ans 记录当前可行值，所以即使二分在取等细节上有差异，只要 check 写得对就不会错。

3.3 死循环是怎么造成的：边界移动的学问

二分最容易出bug的就是死循环。我见过不少人用整数二分时，在某个特殊区间里反复横跳，永远收敛不了。

死循环多半源于两个极端：一个是 mid 计算和边界移动不一致。比如 l = mid 但 mid 又不可能等于 l 的时候，区间长度不变，循环出不来。另一个是使用 l < r 作为循环条件，同时又用了 l = mid 这种更新方式，当 r - l == 1 时，mid 算出来就是 l，check(l) 如果为真，l 还是 l，永远循环。

我的建议是：新手直接使用左闭右闭写法，配上 l = mid + 1 和 r = mid - 1，循环条件写 l <= r，并用 ans 单独记录可行答案。这种写法逻辑最清晰，几乎见不到死循环问题。如果你非要用 l < r 配 l = mid 的写法，那记得 mid 要写成 (l + r + 1) / 2，向上取整，防止区间无法缩小。

3.4 数据规模与输入输出的隐藏陷阱

这道题 N 是 10^6 级别，如果用 cin 不关同步，C++ 的输入可能会吃不少时间。我在代码里加了 ios::sync_with_stdio(false) 和 cin.tie(0)，实测能明显提速。

另外，数组开多大也很关键。题目说 N 最大 10^6，我习惯多开一点点空间，防止访问越界；声明的 a 是 1e6+5 的 long long 数组，足够用了。

最后强调一遍：所有跟高度、木材总量相关的变量都要用 long long。你可能会说“树高不是最多 10^9 吗，int 也能存啊”，但问题出在中间计算 sum 上，多个 10^9 加起来就会超过 2^31 - 1。所以防患于未然，直接全部 long long，一劳永逸。

4. 常见错误与排查技巧实录

4.1 样例过了但提交 WA？先打印中间过程

“样例过了，一交就WA”几乎是所有二分题新手最痛的体验。其实样例只能证明你的代码在某个特定数据下逻辑通顺，不能证明边界处理正确。

我调试砍树题的惯用手段是：如果 WA，就在二分循环里临时加输出，打印 l、r、mid、check(mid) 的返回值，跑几组小数据，人工验证一下区间收缩方向。比如手动构造 N=3, M=10, 树高为 [20, 15, 10] 的例子。check(10) = 10 可行，check(11) = 9 不可行，正确答案就是 10。如果你打印出来的 l、r 移动符合预期，说明思路没错，那就重点检查 check 函数里有没有漏判，比如边界条件多写了一个等号。

4.2 一个典型的错误：check 里用了 int 导致误判

我有个模拟项目里用过这段错误代码，在这里分享给你避坑。当时 N 不大，树高也小，样例全过，但大数据一测试，答案偏小。排查半天发现是 check 函数里 sum 用了 int。当 M 比较小的时候，check 提前返回 true，还没溢出，所以小数据集看着没问题；一旦 M 很大，需要读完整片森林，sum 超过 int 上限，直接变成负数，后续比较 sum >= m 永远为假，导致二分区间整体往低处偏移，最终答案偏小。

这种问题肉眼很难看出来，所以我后来给自己定了一条规矩：凡是可能累加超过 2^31 的量，一律用 long long，不用等到出问题再回头改。

4.3 死循环的现场还原与修复

再分享一个死循环的经典现场。假设代码写成这样：

while (l < r) { int mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid - 1; }

当 check(mid) 为真且 l = r - 1 时，mid = l，更新后 l 还是 l，区间没有变小，循环出不来。这就是纯粹因为更新边界和二分形式不匹配导致的死循环。

修复方式有两种：一种是改成我上面推荐的 l <= r 写法；另一种是保留 l < r，但把 mid 改成 (l + r + 1) / 2，也就是向上取整。为什么向上取整？因为当 l 需要保留为 mid 时，向上取整才能让 l 在必要时大于原来的 l，从而保证区间一定缩小。

4.4 常见问题速查表

4.5 边界测试数据怎么构造

二分题目最容易出事的就是边界附近。我给你几个我经常用来验证的构造思路：

• 所有树一样高，比如 [5, 5, 5]，需要木材为 1，正确答案就是 4。
• 只有一棵树，N=1，树高 1，需要木材 1，正确答案是 0。
• 树高差距极大，比如 [1000000000, 1]，需要木材 1，正确答案是 999999999。
• 所需木材刚好是某个高度下的一部分，检验取等逻辑。

每次把这些边界数据跑一遍，如果你代码都能正确输出，那基本上离 AC 就不远了。

5. 二分答案的进阶视角：从砍树题扩展到一类题

5.1 不只是砍树：二分答案题的通用建模方法

砍树题是二分答案最经典的入门题，但它的价值远远不止“会做这一题”。我前面反复强调的“答案单调性”和“check 函数判断可行性”，可以迁移到大量题目里：比如在一条直线上放置信号塔，求最小覆盖半径；比如把若干本书分给若干个人，求某个人分到的页数最大值的最小值；比如猜数字游戏里用最少的次数锁定某个整数。它们的共性是：要求一个最值，且这个最值具有“可行/不可行”的分界性质。

面对这类题，我建议你按固定步骤思考：先确定二分什么；再思考这个量增大时，约束是否具有单调性；接着写 check 函数，判断给定量是否可行；最后根据 check 结果收缩区间。这个四步法我用了很多年，基本可以解决所有二分答案类问题。

5.2 时间复杂度到底怎么算

二分答案算法的复杂度是 O(N log V)，其中 V 是答案值域的大小。砍树题的值域是 10^9，log2(10^9) 约等于 30，所以实际计算量是 N 乘以 30。N 最大 10^6，总计算量 3000 万，在 C++ 下一般不会超过 1 秒。

很多初学者会纠结：这个复杂度会不会超？你可以直接用经验判断：10^7 级别的计算在 1 秒内没问题，10^8 级别要看常数和评测机，10^9 基本危险。3000 万属于安全范围。

如果你用我代码里的提前剪枝优化，实际遍历次数通常会比 N 少，尤其是 M 较小的时候，速度会更快。所以我在写二分答案题时，check 里只要能提前终止就尽量提前终止。

5.3 我的几点实操体会

做了很多二分答案题之后，我的体会是：二分答案难的不是二分本身，而是 check 函数和边界设计。每次交题前我至少会检查三件事：第一，所有可能累加的数据类型是否足够宽；第二，边界更新和区间形式是否匹配，会不会产生死循环；第三，有没有考虑空木材、恰好满足 M 这类边界条件。

另外，我强烈建议初学者不要背模板，而是每次做题时把 l、r 的含义写在注释里。比如在代码里写清楚“l 表示当前已知可行的高度”，你就会发现二分方向永远不会搞反。我见过太多同学对着模板硬套，一换题就懵，根源就是没有理解边界变量的语义。

提示：如果你刚开始刷二分答案题，建议把这道砍树题当作“模板题”反复手写 3 遍，不要看任何资料。等你能够不假思索地写出正确代码，再去做其他二分答案题，你会发现所谓的新题只是换了一层场景外壳，内核还是那个二分。

最后再分享一个我自己调试时常用的小技巧：如果答案区间很大，想快速验证二分方向是否正确，可以直接用二分中间值打印 check 的返回值，再手动算一组小数据比较。比如树高 [20, 15, 10]，M=10，mid=10 时 check 为 true，mid=14 时 check 为 11，也 true，mid=15 时 check 为 5，false。看到这个走向你就知道，答案落在 10 到 14 之间，二分收缩方向完全正确。这个习惯帮我省下了大量定位 bug 的时间。