最近在OJ上刷题翻到一道编号1908、标题写着【基础】伐木工的题目。第一眼看到基础两个字很多人会直接跳过觉得又是一道送分题。但我在带新人刷题的时候发现恰恰是这类挂着基础标签的二分答案题最能暴露一个人对二分边界、数据溢出、单调性判断这三件事到底有没有真正吃透。它不需要高级数据结构也不需要复杂的状态转移考的纯粹是把一个实际问题抽象成判定二分的能力。这篇就围绕伐木工这道题把从读题到AC的完整链路掰开揉碎讲一遍包括我踩过的坑、写错的模板、以及后来固定下来的一套写法。无论你是刚开始接触二分的新手还是想回头把基础再夯实一遍的老手都能从里面找到对自己有用的东西。1. 这道伐木工到底在考什么1.1 一句话还原题目想让你干的事先把题意讲清楚。伐木工这类题的经典设定是这样的有N棵树排成一排第i棵树的高度是h[i]。伐木工设定一个锯片高度H锯片从下往上推所有高度超过H的树超出部分会被切下来也就是这棵树能贡献h[i] - H的木材高度不超过H的树则一点木材都拿不到。现在给定一个目标木材总量M问在保证总木材量不少于M的前提下锯片高度H最大能设成多少。用一句话概括就是找一个最大的整数H使得所有树贡献的木材之和大于等于M。这就是题目全部的信息量。我第一次看到这个描述的时候脑子里立刻冒出的是枚举H从高到低试一遍第一个满足条件的就是答案。这个思路本身没错问题在于N和树高的数据范围通常不小枚举会把时间直接拉爆。所以真正要做的是从这个问题里看出一个可以二分的单调结构把它降到对数级别。这里我特意强调整数H是因为很多人在实现的时候习惯性用double去二分结果被精度问题反复折磨。既然要求的答案一定落在整数上就老老实实用整数二分别给自己找麻烦。1.2 为什么基础两个字值得单独拎出来说标注为基础通常意味着考点的边界在出题人的预期里是很清晰的就是二分答案不掺杂其他技巧。这种题的检验价值在于它的数据范围往往卡得很巧妙——刚好卡在暴力过不了、正确解法能过的那条线上。我见过太多人提交后拿到TLE第一反应是我算法没错啊然后死活找不到问题实际上是复杂度估算这一环没做扎实。另一个被标基础却常常翻车的地方是边界。二分答案的题目边界处理是重灾区。左边界取0还是取最小值右边界取最大值还是最大值加一mid要不要向上取整这些细节一个没对轻则答案偏一位重则死循环直接超时。而这类错误在小数据上跑样例是看不出来的样例可能碰巧蒙对一到大规模数据就原形毕露。所以这道题真正的训练价值是逼你把二分的边界逻辑从头到尾推明白一次。归纳一下这道题适合三类人练手刚学二分想找一道完整题目练模板的二分总是写挂、边界老出错想系统梳理的以及想通过一道题把单调性分析这个思维动作固化下来的。它的知识门槛不高但对逻辑严谨性的要求一点都不低。2. 核心思路为什么第一时间该想到二分2.1 从猜数字说起二分答案的本质很多人对二分的理解停留在有序数组里找某个数一旦题目没给有序数组就不知道从哪下手了。其实二分的本质跟数组没多大关系它是一个每猜一次就能排除一半可能性的决策过程。你可以想象一个最简单的场景我心里想一个1到100之间的整数你每次报一个数我只告诉你大了小了或者对了。最笨的办法是从1一路报到100平均要五十次聪明的办法是先报50根据我的回答把范围砍掉一半再报75或者25这样最多七次就能锁定答案。这个每次砍一半的过程就是二分。放到伐木工这道题里你要猜的数是H反馈信息是以这个H去砍得到的木材够不够M。够说明H还能再往大试试不够说明H必须往小调。关键点是这个反馈必须是单调的——H越大木材越少这个趋势不能反复横跳否则二分的前提就不成立。这正是下一节要展开的内容。我特别想说的是二分答案和二分查找是两个层次的东西。二分查找是在一个已经有序的东西里找位置而二分答案是在一个答案空间里搜这个空间里的每个候选值都需要现场计算来判定好坏。伐木工属于后者你需要亲手写一个check函数去算某个H到底行不行。想清楚这一层区别做题心态会完全不一样。2.2 单调性这道题能二分的唯一理由单调性是二分答案的命门。我们来看伐木工这道题里H和木材总量之间到底是什么关系。设总木材量为f(H)那么f(H) Σ max(0, h[i] - H)。注意这个求和式里每一项都是关于H的减函数H每增大一点每棵树贡献的木材要么不变当h[i] H时一直是0要么减少当h[i] H时减少相同的量。既然每一项都单调不增加起来当然也单调不增。这就是这道题的单调性来源也是我判断能不能二分的一个固定动作把候选量和结果画成一条曲线看它是不是一路向下或者一路向上。伐木工的f(H)是一条从高处往低处走的阶梯状曲线H从0开始往上涨木材从所有树全部砍掉的总量开始逐渐下降直到H等于最高的树时降为0。有了这条单调递减的曲线问题就转化成了在曲线上找到一个最大的H使得曲线在这个位置的值仍然不低于M。因为曲线是单调的一旦某个H不满足所有比它更大的H就都不满足一旦某个H满足所有比它小的H就都满足。这种二段性——前半段全满足、后半段全不满足——是二分能生效的标志。注意判断单调性的时候一定要把边界情况也想进去。比如M等于0的时候答案是最大的树高锯片设到最高木材为0刚好够M而不是最大值加一。这种极端输入是二分题最容易出错的点。2.3 暴力枚举为什么过不去差在哪我们量化一下暴力到底有多慢。假设树的数量N最多到10的6次方树高的上限到10的9次方。暴力做法是枚举H的每一个可能取值每枚举一个就遍历所有树算一次总木材。单次check的开销是O(N)枚举的范围是O(maxH)两者相乘是10的15次方级别。这个量级就算给足十秒钟也跑不完所以暴力必挂。换成二分之后枚举的次数从maxH降成了log2(maxH)大约是30次。每次check还是O(N)总复杂度降到O(N log maxH)也就是大概3乘10的7次方次基本运算一秒钟之内绰绰有余。这就是二分带来的质变它把逐个试变成了对半砍代价只多了一个写check函数的工作量。这里我习惯用一个经验法则来快速估算只要看到题目里出现最大化某个量或者最小化某个量同时这个量又落在一段连续的整数区间里就条件反射地想一下能不能二分。伐木工正好符合——最大化锯片高度HH的范围是从0到最高树高的一段连续整数。这两个条件凑齐基本可以确定了。3. 实操实现从边界到check函数3.1 二分区间怎么定左右边界的取法二分区间的确定我一般分两步走先问答案最小可能是多少再问答案最大可能是多少。下限这边锯片高度最小可以设成0也就是贴着地面砍这时候所有木材都能拿到但注意如果连M都为0答案还能更大所以0只是一个保守的下界保证不漏解即可。上限这边稍微讲究一点锯片最高可以设成所有树里最高的那棵的高度此时得到0木材如果设得比最高树还高结果还是0木材等于重复了无效区间。所以右边界取maxH是合理的再高就没有意义了。这里有个细节值得说一下也可以把右边界取成maxH 1然后用左闭右开区间去二分但这样会让区间的语义变得绕我不太推荐新手这么写。老老实实用闭区间[0, maxH]左闭右闭逻辑最直观。唯一要记住的配套动作是求最大值时mid要向上取整这个在第4章会专门讲。另外还有一个可以优化但非必须的点下界其实可以取所有树高里的最小值因为当H小于最小树高时每棵树都在贡献木材这些更小的H显然不如最小值附近划算……不过这种优化对复杂度没有本质提升反而容易把边界搞乱。我的建议是保持0作为下界简单可靠性能上完全无所谓。3.2 check函数一行核心逻辑背后的溢出陷阱check函数是整道题的心脏它接收一个候选H返回以这个高度砍木材够不够M。核心就一行对每棵树如果它比H高就把差值累加进总和。bool check(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; }这里面藏着两个坑。第一个是溢出。sum这个累加器必须是long long。为什么假设N是10的6次方每棵树高度是10的9次方最坏情况sum能累到10的15次方而int的上限只有大约2.1乘10的9次方早就爆了。爆掉之后sum变成负数check会一直返回false答案就会偏小而且错得非常隐蔽小数据根本测不出来。同理M和每棵树的h[i]也建议统一用long long存省得来回转换。第二个坑是提前返回。上面代码里加了if (sum m) return true;意思是只要中途累加值已经达标后面就不用算了直接返回真。这个剪枝在大数据下能省不少时间尤其是那些H很小、木材秒达标的情况。不过要注意剪枝只在判断是否达标的场景下成立如果题目要求的不是够不够而是精确总和是多少就不能提前返回。伐木工属于前者可以放心用。注意check函数里千万不能写成h[i] H然后累加h[i] - H这样当h[i]等于H时会累加0虽然结果没错但白白多走一次判断。更重要的是防止有人写反成sum H - h[i]那方向就彻底错了。3.3 完整代码C与Python两版对照给你两版完整代码逻辑完全一致挑你熟悉的用。C版#include bits/stdc.h using namespace std; int n; long long m; vectorlong long h; long long maxH 0; bool check(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() { scanf(%d %lld, n, m); h.resize(n); for (int i 0; i n; i) { scanf(%lld, h[i]); maxH max(maxH, h[i]); } long long lo 0, hi maxH; while (lo hi) { long long mid lo (hi - lo 1) / 2; if (check(mid)) lo mid; else hi mid - 1; } printf(%lld\n, lo); return 0; }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: break if total m: lo mid else: hi mid - 1 print(lo) main()Python这版特意用了sys.stdin.buffer.read()一次性读完再切分比逐行input快很多N大的时候能避免读入成为瓶颈。C那版用scanf而不是cin也是同样的考虑——虽然关掉同步流的cin也够快但scanf更省心不用担心有人忘了写ios::sync_with_stdio(false)。4. 二分模板选型与逐行拆解4.1 求最大值的模板为什么必须向上取整很多人写二分就是记不住什么时候mid (lo hi) / 2什么时候mid (lo hi 1) / 2结果写出来的代码时对时错。我总结过一条特别好记的口诀求满足条件的最大值mid向上取整求满足条件的最小值mid向下取整。为什么求最大值要向上取整我用一个具体的死循环场景来讲。假设当前区间是lo 0hi 1如果你用向下取整mid (0 1) / 2 0。这时候如果check(0)返回真按照求最大值的逻辑应该更新lo mid 0可lo本来就是0区间没有任何缩小下一轮还是lo 0hi 1mid还是0于是永远卡在这里出不去这就是死循环。换成向上取整mid (0 1 1) / 2 1check(1)无论真假都能把区间缩掉一半循环必然终止。反过来求满足条件的最小值时需要用向下取整否则同样会在区间只剩两个数的时候卡住。这个规律不是我编出来的而是从区间必须每轮严格缩小这个硬性要求推出来的理解之后就不用死记了。伐木工求的是最大高度所以用向上取整的模板。4.2 逐行走一遍样例把每一步状态打印出来光看公式容易晕拿一组具体数据走一遍最清楚。设树高为[20, 15, 10, 17]目标木材M 7那么maxH 20初始区间lo 0hi 20。轮次lohimid该高度得到的木材是否≥7区间更新10201010507 22是lo 1021020155002 7是lo 1531520182000 2否hi 1741517164001 5否hi 1551515—循环结束—输出15可以看到第一轮砍到10的时候木材还剩22说明锯片放得太低了完全可以抬高于是下界抬到10第二轮抬到15刚好够7第三轮试18不够说明高度偏高上界压到17第四轮试16也不够上界再压到15。五轮之后区间收敛到单点答案就是15。整个过程只做了四次check而暴力要从0试到20二分至少省了四分之三的工作量数据越大优势越明显。在真正调试的时候如果你怀疑自己的二分出了问题最有效的办法就是像上面这样把每一轮的mid和检查结果打印出来。很多时候不打印不知道一打印就发现是某个边界的更新写反了比如把hi mid - 1写成了hi mid那就直接死循环了。4.3 复杂度与数据范围推算复杂度这块前面提过是O(N log maxH)。我们把它拆开算一遍这样心里有数。每轮的check要遍历N棵树N取10的6次方时是100万次操作二分的轮数是log2(10的9次方)向上取整大约是30轮两者相乘是3000万次基本运算。现代处理器每秒能处理上亿次简单运算所以这个量级非常轻松余量充足。空间上存下所有树高需要一个长度为N的数组也就是10的6次方个long long约8MB完全在常规内存限制之内。如果题目给的内存特别紧张也可以边读边处理但大多数情况下没必要省这点空间。有个容易忽略的点值得提醒如果题目里M给得非常大甚至超过了所有树的总高度那么理论上无解。但正规的题目通常保证有解也就是M不会超过sum(h[i])。如果你写题时遇到一直输出0的情况不妨检查一下M是不是构造得比总高还大或者看看右边界是不是设置得有问题。我在早期刷题时就吃过这个亏以为是二分写错了排查半天才发现是题目给的M超过总木材上限导致任何H都不满足最终返回了初始下界。5. 常见问题与排查技巧实录5.1 死循环与边界错误速查二分题最常见的翻车方式就是死循环机器一直跑不结束最后TLE。我把遇到过的几种死循环成因整理出来你对号入座。第一种是取整方向搞反。求最大值却用了向下取整就会在区间剩两个数时卡住这个前面详细讲过。第二种是区间更新写成了不缩小的形式比如lo mid配向下取整或者hi mid配上取整本质上都是让区间没能严格变小。第三种是初始区间不合法比如lo设得比hi还大或者hi设得太小导致真正的答案落在区间外这种不叫死循环而叫永远找不到正确答案输出会停在一个莫名其妙的值上。还有一种很隐蔽的情况check函数本身有副作用比如在函数内部修改了全局的数组或者累加器导致下一轮的判断基于被污染的数据。这种事在简单题里不常见但一旦发生极难排查。我的做法是check函数尽量写成纯函数只读全局数据不改任何东西。注意调试死循环的时候与其盯着代码看不如在循环里加一个计数器跑超过100次就直接打印当前lo、hi、mid并退出。二分最多几十轮超过这个数肯定是逻辑出问题了让它自己暴露出来比干看快得多。5.2 溢出、效率与几个隐性坑溢出是另一个高频雷区前面在check函数那节提过一次这里再展开讲几个相关点。第一累加器必须用long long这个没得商量。第二读入的时候也要注意格式符匹配C里int用%dlong long用%lldPython里虽然自动处理大整数但如果用numpy之类的库也要留意类型。第三即使单一变量没超中间的计算结果也可能在某一步超掉比如(lo hi)这种加法在某些极端范围下会溢出int所以我在代码里一直用lo (hi - lo 1) / 2这种写法先做减法再加天然规避这个风险。效率方面除了二分本身输入输出往往是大头。N到10的6次方时用cin加不关同步流读入可能会明显变慢用scanf或者关掉同步的cin更稳。Python这边更是如此一定要用sys.stdin.buffer.read()不要用input()一行行读两者差距能有十几倍。这些不是算法问题但直接决定你能不能过最后一个测试点。还有一个隐性坑是提前返回的边界。if (sum m) return true;这个剪枝很好用但如果题目问的稍微变形一下比如要求恰好等于M或者最接近M这个提前返回就不成立了必须老老实实累加到底。所以剪枝能不能加取决于check函数到底在判断什么不能无脑套。5.3 常见问题速查表现象可能原因排查方向程序一直不结束TLEmid取整方向错、区间未严格缩小检查求最大值是否用了向上取整lo/hi的更新是否正确样例能过大测试点WA累加器溢出、边界漏解全部换成long long检查右边界是否够大输出一直是0M超过总木材、右边界设置有问题核对M与总高度的关系检查maxH的初始化答案总是比预期小1右边界偏小、mid取整方向错尝试把上界放宽一位观察结果变化大输入下超时读入慢、check未剪枝改用快读加上sum m的提前返回结果不稳定多次运行不同check函数有副作用、用了未初始化变量把check改成纯函数检查变量初始化这张表我基本是照着多年踩坑记录整理的每次遇到二分题卡住先扫一遍这张表八成能定位到问题。它同时也是我给别人debug时的对照清单效率比自己从头推快得多。5.4 几个能直接抄走的实操心得最后分享几条我反复验证过的小习惯能帮你少走弯路。第一写二分之前先用注释把区间语义写清楚比如// 答案在[lo, hi]内lo是可行下界hi是某个可能不可行的上界。这句话看着废话但它逼你在动手前想清楚边界的含义能拦住一大半边界错误。第二check函数先在草稿纸上用小数据手算一遍确认它对每个H返回的值符合预期再写进代码。第三写完先拿题目给的样例跑一遍再用自己构造的小数据比如只有两棵树、M恰好等于总木材测一遍这两类数据最能逼出边界问题。第四如果时间允许写个暴力版本和二分版本对拍随机生成几十组小数据比较输出一致了再提交。对拍这招在二分题上特别好用因为二分出错往往只在特定边界触发靠人眼很难穷举。这套流程看起来啰嗦但熟练之后也就多花几分钟换来的是几乎不会因为边界问题反复提交。我现在的习惯是凡是涉及二分的题不写对拍不安心。我个人在带新人做这道题时的体会是很多人第一次卡住不是因为不会二分而是没养成先定区间、再写判定、最后调边界这个固定顺序。他们通常是边写边想写到哪算哪结果边界错了都不知道从哪查。把顺序固化下来哪怕慢一点正确率会高出一大截。另外这道题练熟之后可以顺手做一道最小化最大值或最大化最小值的变体比如分绳子、跳石头那一类你会发现它们的骨架和伐木工几乎一模一样只是check函数里换了个判断一通百通。
OJ刷题必看：伐木工二分答案的边界、溢出与单调性全解析
最近在OJ上刷题翻到一道编号1908、标题写着【基础】伐木工的题目。第一眼看到基础两个字很多人会直接跳过觉得又是一道送分题。但我在带新人刷题的时候发现恰恰是这类挂着基础标签的二分答案题最能暴露一个人对二分边界、数据溢出、单调性判断这三件事到底有没有真正吃透。它不需要高级数据结构也不需要复杂的状态转移考的纯粹是把一个实际问题抽象成判定二分的能力。这篇就围绕伐木工这道题把从读题到AC的完整链路掰开揉碎讲一遍包括我踩过的坑、写错的模板、以及后来固定下来的一套写法。无论你是刚开始接触二分的新手还是想回头把基础再夯实一遍的老手都能从里面找到对自己有用的东西。1. 这道伐木工到底在考什么1.1 一句话还原题目想让你干的事先把题意讲清楚。伐木工这类题的经典设定是这样的有N棵树排成一排第i棵树的高度是h[i]。伐木工设定一个锯片高度H锯片从下往上推所有高度超过H的树超出部分会被切下来也就是这棵树能贡献h[i] - H的木材高度不超过H的树则一点木材都拿不到。现在给定一个目标木材总量M问在保证总木材量不少于M的前提下锯片高度H最大能设成多少。用一句话概括就是找一个最大的整数H使得所有树贡献的木材之和大于等于M。这就是题目全部的信息量。我第一次看到这个描述的时候脑子里立刻冒出的是枚举H从高到低试一遍第一个满足条件的就是答案。这个思路本身没错问题在于N和树高的数据范围通常不小枚举会把时间直接拉爆。所以真正要做的是从这个问题里看出一个可以二分的单调结构把它降到对数级别。这里我特意强调整数H是因为很多人在实现的时候习惯性用double去二分结果被精度问题反复折磨。既然要求的答案一定落在整数上就老老实实用整数二分别给自己找麻烦。1.2 为什么基础两个字值得单独拎出来说标注为基础通常意味着考点的边界在出题人的预期里是很清晰的就是二分答案不掺杂其他技巧。这种题的检验价值在于它的数据范围往往卡得很巧妙——刚好卡在暴力过不了、正确解法能过的那条线上。我见过太多人提交后拿到TLE第一反应是我算法没错啊然后死活找不到问题实际上是复杂度估算这一环没做扎实。另一个被标基础却常常翻车的地方是边界。二分答案的题目边界处理是重灾区。左边界取0还是取最小值右边界取最大值还是最大值加一mid要不要向上取整这些细节一个没对轻则答案偏一位重则死循环直接超时。而这类错误在小数据上跑样例是看不出来的样例可能碰巧蒙对一到大规模数据就原形毕露。所以这道题真正的训练价值是逼你把二分的边界逻辑从头到尾推明白一次。归纳一下这道题适合三类人练手刚学二分想找一道完整题目练模板的二分总是写挂、边界老出错想系统梳理的以及想通过一道题把单调性分析这个思维动作固化下来的。它的知识门槛不高但对逻辑严谨性的要求一点都不低。2. 核心思路为什么第一时间该想到二分2.1 从猜数字说起二分答案的本质很多人对二分的理解停留在有序数组里找某个数一旦题目没给有序数组就不知道从哪下手了。其实二分的本质跟数组没多大关系它是一个每猜一次就能排除一半可能性的决策过程。你可以想象一个最简单的场景我心里想一个1到100之间的整数你每次报一个数我只告诉你大了小了或者对了。最笨的办法是从1一路报到100平均要五十次聪明的办法是先报50根据我的回答把范围砍掉一半再报75或者25这样最多七次就能锁定答案。这个每次砍一半的过程就是二分。放到伐木工这道题里你要猜的数是H反馈信息是以这个H去砍得到的木材够不够M。够说明H还能再往大试试不够说明H必须往小调。关键点是这个反馈必须是单调的——H越大木材越少这个趋势不能反复横跳否则二分的前提就不成立。这正是下一节要展开的内容。我特别想说的是二分答案和二分查找是两个层次的东西。二分查找是在一个已经有序的东西里找位置而二分答案是在一个答案空间里搜这个空间里的每个候选值都需要现场计算来判定好坏。伐木工属于后者你需要亲手写一个check函数去算某个H到底行不行。想清楚这一层区别做题心态会完全不一样。2.2 单调性这道题能二分的唯一理由单调性是二分答案的命门。我们来看伐木工这道题里H和木材总量之间到底是什么关系。设总木材量为f(H)那么f(H) Σ max(0, h[i] - H)。注意这个求和式里每一项都是关于H的减函数H每增大一点每棵树贡献的木材要么不变当h[i] H时一直是0要么减少当h[i] H时减少相同的量。既然每一项都单调不增加起来当然也单调不增。这就是这道题的单调性来源也是我判断能不能二分的一个固定动作把候选量和结果画成一条曲线看它是不是一路向下或者一路向上。伐木工的f(H)是一条从高处往低处走的阶梯状曲线H从0开始往上涨木材从所有树全部砍掉的总量开始逐渐下降直到H等于最高的树时降为0。有了这条单调递减的曲线问题就转化成了在曲线上找到一个最大的H使得曲线在这个位置的值仍然不低于M。因为曲线是单调的一旦某个H不满足所有比它更大的H就都不满足一旦某个H满足所有比它小的H就都满足。这种二段性——前半段全满足、后半段全不满足——是二分能生效的标志。注意判断单调性的时候一定要把边界情况也想进去。比如M等于0的时候答案是最大的树高锯片设到最高木材为0刚好够M而不是最大值加一。这种极端输入是二分题最容易出错的点。2.3 暴力枚举为什么过不去差在哪我们量化一下暴力到底有多慢。假设树的数量N最多到10的6次方树高的上限到10的9次方。暴力做法是枚举H的每一个可能取值每枚举一个就遍历所有树算一次总木材。单次check的开销是O(N)枚举的范围是O(maxH)两者相乘是10的15次方级别。这个量级就算给足十秒钟也跑不完所以暴力必挂。换成二分之后枚举的次数从maxH降成了log2(maxH)大约是30次。每次check还是O(N)总复杂度降到O(N log maxH)也就是大概3乘10的7次方次基本运算一秒钟之内绰绰有余。这就是二分带来的质变它把逐个试变成了对半砍代价只多了一个写check函数的工作量。这里我习惯用一个经验法则来快速估算只要看到题目里出现最大化某个量或者最小化某个量同时这个量又落在一段连续的整数区间里就条件反射地想一下能不能二分。伐木工正好符合——最大化锯片高度HH的范围是从0到最高树高的一段连续整数。这两个条件凑齐基本可以确定了。3. 实操实现从边界到check函数3.1 二分区间怎么定左右边界的取法二分区间的确定我一般分两步走先问答案最小可能是多少再问答案最大可能是多少。下限这边锯片高度最小可以设成0也就是贴着地面砍这时候所有木材都能拿到但注意如果连M都为0答案还能更大所以0只是一个保守的下界保证不漏解即可。上限这边稍微讲究一点锯片最高可以设成所有树里最高的那棵的高度此时得到0木材如果设得比最高树还高结果还是0木材等于重复了无效区间。所以右边界取maxH是合理的再高就没有意义了。这里有个细节值得说一下也可以把右边界取成maxH 1然后用左闭右开区间去二分但这样会让区间的语义变得绕我不太推荐新手这么写。老老实实用闭区间[0, maxH]左闭右闭逻辑最直观。唯一要记住的配套动作是求最大值时mid要向上取整这个在第4章会专门讲。另外还有一个可以优化但非必须的点下界其实可以取所有树高里的最小值因为当H小于最小树高时每棵树都在贡献木材这些更小的H显然不如最小值附近划算……不过这种优化对复杂度没有本质提升反而容易把边界搞乱。我的建议是保持0作为下界简单可靠性能上完全无所谓。3.2 check函数一行核心逻辑背后的溢出陷阱check函数是整道题的心脏它接收一个候选H返回以这个高度砍木材够不够M。核心就一行对每棵树如果它比H高就把差值累加进总和。bool check(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; }这里面藏着两个坑。第一个是溢出。sum这个累加器必须是long long。为什么假设N是10的6次方每棵树高度是10的9次方最坏情况sum能累到10的15次方而int的上限只有大约2.1乘10的9次方早就爆了。爆掉之后sum变成负数check会一直返回false答案就会偏小而且错得非常隐蔽小数据根本测不出来。同理M和每棵树的h[i]也建议统一用long long存省得来回转换。第二个坑是提前返回。上面代码里加了if (sum m) return true;意思是只要中途累加值已经达标后面就不用算了直接返回真。这个剪枝在大数据下能省不少时间尤其是那些H很小、木材秒达标的情况。不过要注意剪枝只在判断是否达标的场景下成立如果题目要求的不是够不够而是精确总和是多少就不能提前返回。伐木工属于前者可以放心用。注意check函数里千万不能写成h[i] H然后累加h[i] - H这样当h[i]等于H时会累加0虽然结果没错但白白多走一次判断。更重要的是防止有人写反成sum H - h[i]那方向就彻底错了。3.3 完整代码C与Python两版对照给你两版完整代码逻辑完全一致挑你熟悉的用。C版#include bits/stdc.h using namespace std; int n; long long m; vectorlong long h; long long maxH 0; bool check(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() { scanf(%d %lld, n, m); h.resize(n); for (int i 0; i n; i) { scanf(%lld, h[i]); maxH max(maxH, h[i]); } long long lo 0, hi maxH; while (lo hi) { long long mid lo (hi - lo 1) / 2; if (check(mid)) lo mid; else hi mid - 1; } printf(%lld\n, lo); return 0; }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: break if total m: lo mid else: hi mid - 1 print(lo) main()Python这版特意用了sys.stdin.buffer.read()一次性读完再切分比逐行input快很多N大的时候能避免读入成为瓶颈。C那版用scanf而不是cin也是同样的考虑——虽然关掉同步流的cin也够快但scanf更省心不用担心有人忘了写ios::sync_with_stdio(false)。4. 二分模板选型与逐行拆解4.1 求最大值的模板为什么必须向上取整很多人写二分就是记不住什么时候mid (lo hi) / 2什么时候mid (lo hi 1) / 2结果写出来的代码时对时错。我总结过一条特别好记的口诀求满足条件的最大值mid向上取整求满足条件的最小值mid向下取整。为什么求最大值要向上取整我用一个具体的死循环场景来讲。假设当前区间是lo 0hi 1如果你用向下取整mid (0 1) / 2 0。这时候如果check(0)返回真按照求最大值的逻辑应该更新lo mid 0可lo本来就是0区间没有任何缩小下一轮还是lo 0hi 1mid还是0于是永远卡在这里出不去这就是死循环。换成向上取整mid (0 1 1) / 2 1check(1)无论真假都能把区间缩掉一半循环必然终止。反过来求满足条件的最小值时需要用向下取整否则同样会在区间只剩两个数的时候卡住。这个规律不是我编出来的而是从区间必须每轮严格缩小这个硬性要求推出来的理解之后就不用死记了。伐木工求的是最大高度所以用向上取整的模板。4.2 逐行走一遍样例把每一步状态打印出来光看公式容易晕拿一组具体数据走一遍最清楚。设树高为[20, 15, 10, 17]目标木材M 7那么maxH 20初始区间lo 0hi 20。轮次lohimid该高度得到的木材是否≥7区间更新10201010507 22是lo 1021020155002 7是lo 1531520182000 2否hi 1741517164001 5否hi 1551515—循环结束—输出15可以看到第一轮砍到10的时候木材还剩22说明锯片放得太低了完全可以抬高于是下界抬到10第二轮抬到15刚好够7第三轮试18不够说明高度偏高上界压到17第四轮试16也不够上界再压到15。五轮之后区间收敛到单点答案就是15。整个过程只做了四次check而暴力要从0试到20二分至少省了四分之三的工作量数据越大优势越明显。在真正调试的时候如果你怀疑自己的二分出了问题最有效的办法就是像上面这样把每一轮的mid和检查结果打印出来。很多时候不打印不知道一打印就发现是某个边界的更新写反了比如把hi mid - 1写成了hi mid那就直接死循环了。4.3 复杂度与数据范围推算复杂度这块前面提过是O(N log maxH)。我们把它拆开算一遍这样心里有数。每轮的check要遍历N棵树N取10的6次方时是100万次操作二分的轮数是log2(10的9次方)向上取整大约是30轮两者相乘是3000万次基本运算。现代处理器每秒能处理上亿次简单运算所以这个量级非常轻松余量充足。空间上存下所有树高需要一个长度为N的数组也就是10的6次方个long long约8MB完全在常规内存限制之内。如果题目给的内存特别紧张也可以边读边处理但大多数情况下没必要省这点空间。有个容易忽略的点值得提醒如果题目里M给得非常大甚至超过了所有树的总高度那么理论上无解。但正规的题目通常保证有解也就是M不会超过sum(h[i])。如果你写题时遇到一直输出0的情况不妨检查一下M是不是构造得比总高还大或者看看右边界是不是设置得有问题。我在早期刷题时就吃过这个亏以为是二分写错了排查半天才发现是题目给的M超过总木材上限导致任何H都不满足最终返回了初始下界。5. 常见问题与排查技巧实录5.1 死循环与边界错误速查二分题最常见的翻车方式就是死循环机器一直跑不结束最后TLE。我把遇到过的几种死循环成因整理出来你对号入座。第一种是取整方向搞反。求最大值却用了向下取整就会在区间剩两个数时卡住这个前面详细讲过。第二种是区间更新写成了不缩小的形式比如lo mid配向下取整或者hi mid配上取整本质上都是让区间没能严格变小。第三种是初始区间不合法比如lo设得比hi还大或者hi设得太小导致真正的答案落在区间外这种不叫死循环而叫永远找不到正确答案输出会停在一个莫名其妙的值上。还有一种很隐蔽的情况check函数本身有副作用比如在函数内部修改了全局的数组或者累加器导致下一轮的判断基于被污染的数据。这种事在简单题里不常见但一旦发生极难排查。我的做法是check函数尽量写成纯函数只读全局数据不改任何东西。注意调试死循环的时候与其盯着代码看不如在循环里加一个计数器跑超过100次就直接打印当前lo、hi、mid并退出。二分最多几十轮超过这个数肯定是逻辑出问题了让它自己暴露出来比干看快得多。5.2 溢出、效率与几个隐性坑溢出是另一个高频雷区前面在check函数那节提过一次这里再展开讲几个相关点。第一累加器必须用long long这个没得商量。第二读入的时候也要注意格式符匹配C里int用%dlong long用%lldPython里虽然自动处理大整数但如果用numpy之类的库也要留意类型。第三即使单一变量没超中间的计算结果也可能在某一步超掉比如(lo hi)这种加法在某些极端范围下会溢出int所以我在代码里一直用lo (hi - lo 1) / 2这种写法先做减法再加天然规避这个风险。效率方面除了二分本身输入输出往往是大头。N到10的6次方时用cin加不关同步流读入可能会明显变慢用scanf或者关掉同步的cin更稳。Python这边更是如此一定要用sys.stdin.buffer.read()不要用input()一行行读两者差距能有十几倍。这些不是算法问题但直接决定你能不能过最后一个测试点。还有一个隐性坑是提前返回的边界。if (sum m) return true;这个剪枝很好用但如果题目问的稍微变形一下比如要求恰好等于M或者最接近M这个提前返回就不成立了必须老老实实累加到底。所以剪枝能不能加取决于check函数到底在判断什么不能无脑套。5.3 常见问题速查表现象可能原因排查方向程序一直不结束TLEmid取整方向错、区间未严格缩小检查求最大值是否用了向上取整lo/hi的更新是否正确样例能过大测试点WA累加器溢出、边界漏解全部换成long long检查右边界是否够大输出一直是0M超过总木材、右边界设置有问题核对M与总高度的关系检查maxH的初始化答案总是比预期小1右边界偏小、mid取整方向错尝试把上界放宽一位观察结果变化大输入下超时读入慢、check未剪枝改用快读加上sum m的提前返回结果不稳定多次运行不同check函数有副作用、用了未初始化变量把check改成纯函数检查变量初始化这张表我基本是照着多年踩坑记录整理的每次遇到二分题卡住先扫一遍这张表八成能定位到问题。它同时也是我给别人debug时的对照清单效率比自己从头推快得多。5.4 几个能直接抄走的实操心得最后分享几条我反复验证过的小习惯能帮你少走弯路。第一写二分之前先用注释把区间语义写清楚比如// 答案在[lo, hi]内lo是可行下界hi是某个可能不可行的上界。这句话看着废话但它逼你在动手前想清楚边界的含义能拦住一大半边界错误。第二check函数先在草稿纸上用小数据手算一遍确认它对每个H返回的值符合预期再写进代码。第三写完先拿题目给的样例跑一遍再用自己构造的小数据比如只有两棵树、M恰好等于总木材测一遍这两类数据最能逼出边界问题。第四如果时间允许写个暴力版本和二分版本对拍随机生成几十组小数据比较输出一致了再提交。对拍这招在二分题上特别好用因为二分出错往往只在特定边界触发靠人眼很难穷举。这套流程看起来啰嗦但熟练之后也就多花几分钟换来的是几乎不会因为边界问题反复提交。我现在的习惯是凡是涉及二分的题不写对拍不安心。我个人在带新人做这道题时的体会是很多人第一次卡住不是因为不会二分而是没养成先定区间、再写判定、最后调边界这个固定顺序。他们通常是边写边想写到哪算哪结果边界错了都不知道从哪查。把顺序固化下来哪怕慢一点正确率会高出一大截。另外这道题练熟之后可以顺手做一道最小化最大值或最大化最小值的变体比如分绳子、跳石头那一类你会发现它们的骨架和伐木工几乎一模一样只是check函数里换了个判断一通百通。
