你看到“砍树”这道二分答案题第一反应是不是“这有什么好讲的不就是套个二分模板”但说真的我见过太多人在 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 次判断哪怕每次判断要扫描一遍 N10^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 算出来就是 lcheck(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 是 1e65 的 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) 的返回值跑几组小数据人工验证一下区间收缩方向。比如手动构造 N3, M10, 树高为 [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 常见问题速查表症状可能原因解决办法死循环mid 取整方向与边界更新方式不匹配统一为 lr 配 mid(lr)/2或用 lr 配 mid(lr1)/2答案偏小check 中 sum 溢出将 sum、H、树高都改为 long long答案偏大循环条件错误多更新了一步检查 r mid - 1 是否正确检查 ans 是否只在 check 成功时更新超时cin 未关同步流使用 ios::sync_with_stdio(false); cin.tie(0);初值错误上界设成题目给的最大高度而非树的最大高度输入时记录 maxH 作为右边界4.5 边界测试数据怎么构造二分题目最容易出事的就是边界附近。我给你几个我经常用来验证的构造思路所有树一样高比如 [5, 5, 5]需要木材为 1正确答案就是 4。只有一棵树N1树高 1需要木材 1正确答案是 0。树高差距极大比如 [1000000000, 1]需要木材 1正确答案是 999999999。所需木材刚好是某个高度下的一部分检验取等逻辑。每次把这些边界数据跑一遍如果你代码都能正确输出那基本上离 AC 就不远了。5. 二分答案的进阶视角从砍树题扩展到一类题5.1 不只是砍树二分答案题的通用建模方法砍树题是二分答案最经典的入门题但它的价值远远不止“会做这一题”。我前面反复强调的“答案单调性”和“check 函数判断可行性”可以迁移到大量题目里比如在一条直线上放置信号塔求最小覆盖半径比如把若干本书分给若干个人求某个人分到的页数最大值的最小值比如猜数字游戏里用最少的次数锁定某个整数。它们的共性是要求一个最值且这个最值具有“可行/不可行”的分界性质。面对这类题我建议你按固定步骤思考先确定二分什么再思考这个量增大时约束是否具有单调性接着写 check 函数判断给定量是否可行最后根据 check 结果收缩区间。这个四步法我用了很多年基本可以解决所有二分答案类问题。5.2 时间复杂度到底怎么算二分答案算法的复杂度是 O(N log V)其中 V 是答案值域的大小。砍树题的值域是 10^9log2(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]M10mid10 时 check 为 truemid14 时 check 为 11也 truemid15 时 check 为 5false。看到这个走向你就知道答案落在 10 到 14 之间二分收缩方向完全正确。这个习惯帮我省下了大量定位 bug 的时间。