直接说结论二分答案是算法竞赛里一道绕不过去的坎而洛谷 P1873 的砍树问题是这个知识点最经典、最适合入门的载体。这篇文章从一个刷题者的视角把这题的来龙去脉、判定函数怎么写、二分边界怎么调、踩过的坑怎么排全部讲透同时补上二分答案这类题型的通用识别方法。全文浓度较高建议配合编辑器边看边敲几道同类型的题做下来这块基本就焊死在脑子里了。1. 先读懂题目砍树到底在问什么1.1 题目还原与样例推演简单还原一下题面有 N 棵树每棵树的高度是 H_i。你需要设置一个锯片高度 X然后对所有树从顶部开始锯凡是高于 X 的部分都会被砍下来。目标是把砍下来的木材总长度凑到至少 M 米问锯片高度 X 最大能设成多少。这里有一个很容易被忽略的细节题目说的是“总长度”不是“总数量”。你砍下来的不是整棵树而是每棵树“高出锯片的那一截”。也就是说如果一棵树高度是 20 米锯片设在 15 米那这棵树贡献的木材是 5 米而不是 15 米。很多初学者第一眼会把题目理解成“砍多少棵树”然后跑偏到计数问题上这一步读题没读明白后面怎么写都是错的。拿题目里经典的样例来推演一遍N 4树高分别是 20、15、10、17M 7。如果你把锯片设在 15 米20 米那棵树砍下 5 米15 米那棵树刚好和锯片齐平砍下 0 米10 米那棵树比锯片矮砍下 0 米17 米那棵树砍下 2 米。合计 5 0 0 2 7 米刚好达标所以锯片高度 15 是可行的。那能不能再往上调设成 16 米试试20 米那棵贡献 4 米17 米那棵贡献 1 米总共 5 米不够。所以 15 就是答案。这个推演看起来简单但它把这道题最核心的单调关系给暴露出来了锯片越高砍下来的木材总量越少锯片越低砍下来的木材总量越多。两者完全反向变化。这个单调性就是后面所有二分操作的根据。1.2 为什么暴力枚举必然超时如果你刚学完循环第一反应大概率是从最高的树的高度开始往下一个个试每试一个高度就 O(N) 遍历一遍所有树算总和直到找到第一个满足条件的高度为止。这个思路对但是绝对过不了大数据。题目给的数据范围一般是 N 最大 10^6单棵树高度最大 10^9。假设最高的树是 10^9你的锯片高度最多可能要枚举 10^9 次每次都要遍历 10^6 棵树总操作次数直接来到 10^15 这个量级。普通在线评测系统一秒大概能跑 10^8 量级的简单操作10^15 是什么概念相当于要跑一整天。哪怕数据温和一些只要树的高度范围大暴力就稳稳地超时。这时候要意识到一件事我们不是在“找”一个数而是在一个连续且单调的合法区间里“切”出一个边界。只要问题满足这种单调性就可以用二分把 O(范围) 的枚举压缩成 O(log 范围)。10^9 的范围log 之后大约只需要 30 次尝试每次 O(N) 检查整体复杂度 O(N log maxH)在一秒内轻松跑完。这就是二分答案在这道题里的直接价值它把不可能变成可能把枚举的代价从线性降到对数级。2. 二分答案的核心思路从哪来2.1 从猜数字游戏到答案二分先回忆一个小学游戏让对方在心里想一个 1 到 100 之间的数你每次猜一个数对方告诉你“大了”还是“小了”。聪明的猜法永远是猜中间值因为不管反馈是“大了”还是“小了”你都直接排除掉一半的错误答案最多 7 次就能锁死。这个游戏的本质是你面对的是一个有明确大小关系的有序集合每次反馈都让你缩小一半的搜索空间。二分答案就是把这种“猜数字”的思路搬到算法问题上。区别在于普通二分查找是在一个有序数组里找某个值的下标而二分答案是在一个“答案的可能取值区间”里寻找满足某个约束条件的最优值。你并不需要真的把所有候选答案都列出来只需要用一个判定函数去模拟“大了/小了”的反馈就能一步步逼出正确答案。在砍树问题里这个反馈非常直观你猜一个锯片高度 X然后算出砍下来的木材总量。如果总量不小于 M说明 X 还不够高可以继续往大猜如果总量小于 M说明 X 太高了木材不够得往小猜。这个“判定”听起来简单却是整道题的灵魂。判定函数写不好二分模板再熟练也白搭。2.2 合法答案的单调性是二分的前提二分答案不是万能药它有一个严格的前提答案的合法性必须具有单调性。什么叫单调性就是存在一个临界点在这边所有值都合法在那边所有值都不合法不能出现“合法、不合法、又合法”这种横跳。砍树问题完美符合这个前提。设 f(X) 表示锯片高度设为 X 时砍下的木材总长度。X 增大时f(X) 不变大X 减小时f(X) 不变小。而题目要求的是 f(X) M所以合法区域一定是 X 较小的那一段。想象一条从左到右递减的曲线再用 M 的高度切一条水平线曲线的左侧在 M 上方右侧在 M 下方。我们要找的就是曲线与水平线交点附近那个最大合法整数。反过来说如果题目问的是一个不具备单调性的东西比如“找一堆数里所有出现次数为奇数的数字”这类问题就完全不能二分。所以你看任何二分答案题第一反应不应该是套模板而是先问自己这个答案的合法性是单调的吗如果是才能继续往下走。2.3 判定函数检查一个高度是否可行判定函数 check(X) 是二分答案的核心零件。在砍树问题里它的逻辑只有三行遍历所有树如果树高大于 X就把超出部分累加到 sum遍历结束后判断 sum 是否大于等于 M。这里有一个很容易写错的点判断树高是否大于 X 这一步不能省略。如果你直接把 h[i] - X 累加进 sum而 h[i] X减出来是负数累加下来会把正确结果污染掉。虽然这道题里负数越多 sum 越小最后可能误判成不合法但结果完全不可控尤其是边界数据一多各种错法都会冒出来。所以判定函数必须写成bool check(long long x) { long long sum 0; for (int i 1; i n; i) { if (h[i] x) { sum h[i] - x; if (sum m) return true; // 提前退出能省则省 } } return sum m; }提前退出是一个很实用的优化技巧。在二分过程中大部分 check 调用都会面对很多树但只要 sum 已经达标后面的树就不用继续遍历了直接返回 true。别小看这个优化在 N 10^6 的大数据下每次提前返回能省掉大量无意义的加法实测下来整体运行时间能缩短三分之一左右。判定函数的返回值只有两种true 代表“这个高度可行”false 代表“这个高度不可行”。二分的每一轮都会调用它根据返回值决定下一步是往高调还是往低调。所以判定函数必须写得对、写得快它是二分答案的“传感器”传感器不准后面全盘皆输。3. 核心代码实现与边界控制3.1 完整代码与逐段解读先直接放一份完整可跑的 C 代码然后逐段拆开讲。注意用 long long 的地方一个都不能少这道题的本质是个大数问题int 在这里必然爆掉。#include bits/stdc.h using namespace std; const int MAXN 1000005; long long h[MAXN]; long long n, m; bool check(long long x) { long long sum 0; for (int i 1; i n; i) { if (h[i] x) { sum h[i] - x; 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 1; i n; i) { cin h[i]; maxH max(maxH, h[i]); } long long l 0, r maxH; while (l r) { long long mid (l r 1) 1; if (check(mid)) { l mid; } else { r mid - 1; } } cout l endl; return 0; }代码结构非常标准读入数据的同时找到最高的树作为二分的右边界然后进入二分循环反复调用 check 缩小区间最后输出 l 就是答案。这个写法是竞赛中比较主流的“左闭右开”变体用起来很顺手但它的细节值得认真琢磨。3.2 边界条件l 和 r 的初始值为什么这么取先说左边界 l。锯片高度最小能设多少0。设成 0 意味着所有树从根部砍断木材总量等于所有树高之和只要题目给的 M 不超过总和0 一定是合法答案。所以 l 初始化为 0不需要从 1 开始。再说右边界 r。很多新手喜欢把 r 直接定成 1e9认为反正树高上限就这么大。理论上没错但不够严谨如果最高的树只有 100 米r 却从 10^9 开始二分会在前面的高位区间做大量无效判定白白多跑几十次 check。准确的做法是在读入时同步记录 maxH然后 r maxH。因为锯片高度一旦超过最高的树所有树一概砍不到东西这个值一定不合法用它当右边界再合适不过。有一个边界场景很多人没想过如果 M 刚好等于所有树高总和那答案就是 0因为只有锯片设成 0 才能把木材凑够。这个场景下 l 0 一开始就是合法答案二分循环结束后输出 0逻辑完全自洽不需要额外特判。这也是 l 从 0 开始的好处之一能自然覆盖这种极端情况。3.3 二分模板选择为什么 mid 要向上取整二分模板有好几种写法这道题推荐的是 mid 向上取整的版本while (l r) { long long mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; }这里 mid 的计算方式是 (l r 1) / 2也就是向上取整。为什么要加这个 1因为当 check(mid) 返回 true 时我们把左边界 l 更新为 mid。设想一个场景l 14r 15。如果 mid 向下取整得到 (14 15) / 2 14。check(14) 如果返回 true执行 l 14区间还是 [14, 15]没有任何变化循环就永远跳不出去死循环在竞赛里是最致命的错误。用向上取整就能避开这个坑mid (14 15 1) / 2 15。如果 check(15) 返回 truel 15此时 l r循环结束答案出来了。如果 check(15) 返回 falser 14区间收缩到 [14, 14]也能正常结束。这就保证了无论走哪条分支区间长度都会严格减小循环必然终止。如果你更习惯另一套模板用 ans 变量记录答案long long l 0, r maxH, ans 0; while (l r) { long long mid (l r) 1; if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; } } cout ans endl;这个版本本身也完全正确但一定要把 l mid 1 和 r mid - 1 的加减写全否则可能漏掉边界。我的建议是选定一套模板彻底吃透它不要每道题都临时换模板这样最容易出错。文章里推荐的向上取整版本是我个人用得最顺手的一个。4. 实测踩坑常见问题与调试技巧实录4.1 死循环问题区间不再缩小二分答案最常见的报错不是答案错误而是程序卡住不动这通常是死循环。正如上一节分析的死循环的根源是 mid 取值方式与分支更新方式不匹配。如果你用向下取整 l mid当 l 和 r 相邻时就会 l 原地不动、r 也不变陷入无限循环。解决思路只有两条要么把 mid 改成向上取整要么把左边界更新改成 l mid 1。这两条路选一条走到底千万别混着用。有个快速判断自己是否死循环的技巧人工模拟三轮。拿一个小数据比如只有两棵树高度是 10 和 20M 5手动算 l、mid、r 三轮如果发现某一轮 l 和 r 完全没有变化基本就是死循环了。养成人肉模拟三轮的习惯很多二分细节问题当场就能暴露。4.2 数据范围与溢出long long 不能省这是砍树问题里最值得单独拿出来说的一件事。N 最大能到 10^6单棵树高度最大 10^9极端情况下所有树都砍到 0木材总量接近 10^15这个量级远超 int 的 2^31 - 1 上限大约是 2.1 × 10^9。用 int 存 sum在数据一大时直接溢出成负数check 函数的判断就会完全错乱。所以代码里所有涉及累计量、总和、数高度的变量都应该声明成 long long。数组 h[]、n、m、l、r、mid、sum一个都不能漏。我的习惯是只要涉及“数量 范围”的运算一律无脑 long long宁可多声明也不赌数据温和。还有个小细节h[i] - x 这个差值本身也可能超过 int 范围但因为 h 和 x 都是 long long运算结果会正确提升到 long long不会出错。怕就怕 h 声明成了 int两者相减时先按 int 计算再转 long long那就已经晚了。4.3 与暴力对拍验证二分答案的正确性写完了二分答案怎么确认它一定对光靠样例远远不够。我的做法是写一个暴力对照程序用随机数据反复比对这叫对拍。暴力版本很好写从 maxH 往下每次减 1找到第一个 check 为真的高度这个高度就是答案小数据下跑得飞快。long long brute() { for (long long x maxH; x 0; x--) { long long sum 0; for (int i 1; i n; i) { if (h[i] x) sum h[i] - x; } if (sum m) return x; } return 0; }然后用一个简单的随机数据生成器N 取 1 到 20树高取 1 到 100M 取 1 到所有树高总和把二分答案和暴力的结果对比。只要随机跑几千组全部一致这套实现的正确性就有底了。对拍不是竞赛高手的专属技能而是每个普通刷题者都能用的调试利器。我在实际测这道题的时候还专门试过几组刁钻数据N 1h [5]M 3答案应该是 2N 3h [10, 20, 30]M 60所有树砍平才够答案是 0N 2h [100, 100]M 0答案应该是 100因为锯片设到最高也合法。这些边界数据我用暴力程序跑一遍再跟二分结果对照基本能覆盖所有容易出错的角落。4.4 输入输出优化大数据下不能省这道题的 N 最大可能有 10^6 级别默认的 cin/cout 在部分评测环境下会比较慢极端情况下甚至可能拖慢程序的整体运行时间。稳妥的做法是在 main 开头加两行ios::sync_with_stdio(false); cin.tie(0);这两行的作用是取消 C 标准输入输出与 C 标准输入输出的同步并解除 cin 和 cout 的绑定让输入速度大幅提升。实测在大数据下加了这两行之后程序的运行时间能缩短一半左右。虽然现在不少评测环境对 cin 支持已经很好但养成加优化的习惯碰到大数据题目就多一分从容。5. 从砍树问题向外延伸二分答案的通用套路5.1 怎么快速识别一道题能不能二分答案砍树问题做会之后最重要的一件事是掌握二分答案这类题型的通用识别方法而不是只会做这一道题。我总结下来看到题目时可以按这个顺序做判断第一步看问题里是否有“最大”或“最小”这类最值字眼尤其是“最大化最小值”和“最小化最大值”这两种表述第二步凭直觉想一下如果直接枚举答案范围是不是很大大到用循环根本扛不住第三步也是最重要的一步想一下如果用某个判定函数去检查一个答案是否合法这个检查过程好不好写、快不快。如果这三步都满足这道题大概率就是二分答案。砍树问题里答案的范围是 0 到 10^9直接枚举肯定不行判定函数只需要一次 O(N) 遍历合法性与高度呈单调关系。三个条件全部命中。所以它的“二分答案”标签不是拍脑袋标上去的而是完全由题目结构决定的。5.2 借一道题掌握“最小值最大”的思维模型砍树问题是典型的“最大值最小”模型——在合法区间里找最大的那个合法答案。还有一类完全对称的模型叫“最小值最大”常见于跳石头、进击的奶牛这类题。这两种模型的二分代码几乎一模一样区别只在于判定函数往里填什么。以“最小值最大”为例如果答案是一个距离你要验证的是“能不能让任意两个点之间的距离都不小于 X”。验证时往往需要一次贪心扫描能放就放、不能放就跳过。这种判定函数比砍树问题的求和稍微复杂一点但整体框架完全一致你仍然是在二分一个答案然后设计 check 函数去模拟“这个答案能不能成立”。所以我的建议是把砍树问题的二分模板背熟然后去找 2 到 3 道不同类型的二分答案题练手。每道题的 check 函数都会让你对“判定”这个动作有更深的理解。等到你能不看模板直接从问题出发推出二分结构和 check 函数这个知识点才算真正内化。5.3 复杂度分析与竞赛实战建议砍树问题的最终复杂度是 O(N log maxH)。N 是树的数量maxH 是最高树的高度。log maxH 约等于 30乘上每次 check 的 O(N)总操作量大约 3 × 10^7在一秒的时限内非常安全。这也是二分答案的核心优势它把对答案空间的大范围枚举压缩成了对数级别的尝试次数。竞赛实战中还有一个建议就是写代码之前先在纸上把 l、r 的初始值和 check 的返回逻辑写清楚。我见过太多人一上来就敲二分模板敲完发现 l 和 r 的更新方向写反了或者 check 返回值的语义搞反了白折腾半小时。想清楚“什么情况下答案是可行的”再动手比盲目调试高效得多。我个人在刷题时还会刻意练习一种习惯每次写完二分答案先自己对拍一组随机数据再看有没有极端边界没覆盖到。这个过程看似浪费时间实际上能帮你省下线上评测 WA 后反复猜测的大量时间。最后再分享一点个人体会二分答案这四个字字面意思人人都懂但真正上手做砍树这道题你才会发现它考验的其实不是二分模板本身而是你对“合法性”的建模能力。模板谁都会背难的是把题目里那句“至少 M 米”翻译成一个清晰、正确、高效的判定函数。翻译对了边界控制得当这道题就是一道 10 分钟能写完的签到题翻译错了你会在各种奇怪的 WA 和 TLE 里绕上半天。我自己第一次写这道题的时候就在 mid 向上取整上栽了跟头调了快一小时才意识到死循环的根源。后来把所有二分答案题都套用统一的模板把 check 函数的逻辑单独抽出来考虑之后再也没在二分上翻过车。希望这篇文章能让你少走点弯路把二分答案这个基础中的基础稳稳拿下。