題庫里編號 1908 的這道《伐木工》標(biāo)簽上就倆字——基礎(chǔ)。但我見過太多人在這道基礎(chǔ)題上栽跟頭要么二分寫成了死循環(huán)交上去一直是那個刺眼的紅字要么判定函數(shù)里用了 int被一組幾十萬棵樹、每棵高上億的數(shù)據(jù)直接干翻。它之所以被放在基礎(chǔ)區(qū)不是因為簡單而是因為它把二分答案這套方法的每一個坑都擺在了最顯眼的位置上。把這道題吃透你后面遇到的最大值最小最小值最大類問題基本都能靠同一套肌肉記憶解決。下面我就按自己平時解題和講課的順序從建模、選型、邊界、代碼、對拍到變式完整地拆一遍。適合剛學(xué)二分的新手也適合想回頭查漏補(bǔ)缺的老手。1. 題目模型拆解與算法選型思路1.1 把砍樹這件事翻譯成一句數(shù)學(xué)命題先把題面用大白話還原一遍場上立著 n 棵樹第 i 棵樹的高度是 h_i。伐木工把鋸子水平架在某個高度 H 上凡是比 H 高的樹高于 H 的那一截被整體切下來變成木材長度就是 h_i 減去 H凡是本身就不超過 H 的樹一根木頭都產(chǎn)不出來?，F(xiàn)在要求這些木材的總長度加起來不少于 m問這個 H 最大能架多高。轉(zhuǎn)成數(shù)學(xué)語言就是求滿足 Σ max(0, h_i ? H) ≥ m 的最大的整數(shù) H。這一步轉(zhuǎn)譯是整個解題過程里最關(guān)鍵的一步很多人寫不出來不是不會二分而是沒把中文題面精確地翻譯成含絕對值或者取最大值的式子。我個人的經(jīng)驗是讀題之后一定先強(qiáng)迫自己寫出這條不等式寫在草稿紙最上面后面所有的邊界討論都圍繞它展開。生活里有個特別貼切的類比這就像往一個不規(guī)則的容器里舀水水位線壓得越低能舀出來的水越多水位線抬得越高舀出來的水越少。H 就是那條水位線產(chǎn)出木材總量關(guān)于 H 是嚴(yán)格遞減的關(guān)系我們要找的就是剛好還夠舀出 m 這么多水的那條最高水位線。1.2 為什么第一反應(yīng)不該是從高往低枚舉最樸素的思路非常誘人H 從最高的樹開始每次減一算一遍總產(chǎn)出第一個滿足條件的就是答案。思路沒錯復(fù)雜度也一目了然——枚舉次數(shù)最多是 max(h) 次每次判定要掃一遍 n 棵樹總復(fù)雜度 O(n · max h)。問題出在數(shù)據(jù)規(guī)模上。當(dāng) n 只有 1000、樹高不超過 1000 的時候這個暴力是 10^6 量級隨便跑可一旦 n 漲到 10^5、樹高上限到 10^9暴力就是 10^14 次基本操作別說一秒給你一小時都跑不完。這時候必須換思路。我教新人的時候常說一句話只要你在題目里看到最大/最小配上滿足某個數(shù)量條件而且那個條件的可行性是單調(diào)的那九成九是二分答案。這道題就是最標(biāo)準(zhǔn)的模板連變形的余地都沒有。1.3 單調(diào)性證明二分答案真正的通行證很多人用二分答案是背模板問他為什么能二分答不上來。這道基礎(chǔ)題恰好是練證明的好材料證明只有一行假設(shè)高度 H 是可行的那么對任意 H′ H因為 h_i ? H′ ≥ h_i ? H 對每一棵樹都成立所以 H′ 處的總產(chǎn)出 ≥ H 處的總產(chǎn)出 ≥ m也就是說 H′ 必然也可行。這句話翻譯過來就是可行的高度集合一定是一個從 0 開始的連續(xù)前綴區(qū)間 [0, H*]不存在中間可行、兩邊不可行這種坑爹形態(tài)。有一側(cè)單調(diào)就能二分這是二分答案能成立的全部地基。提示二分答案的前提從來不是題目看起來像二分而是判定函數(shù)關(guān)于答案具有單調(diào)性。寫完代碼前先在草稿紙上把這段證明寫出來比事后對拍一百組數(shù)據(jù)都管用。1.4 判定函數(shù)把優(yōu)化問題降級成判斷題二分答案的通用套路是把求最優(yōu)值轉(zhuǎn)成判定是否可行。這道題里check(H) 的任務(wù)非常干凈給定一個高度 H算一算總產(chǎn)出夠不夠 m返回 true 或者 false。原本讓人頭疼的最大化 H問題被拆成了大約三十次夠不夠的是非題。這個思路的價值在于降維。找出最大值往往需要巧思而判斷某個給定方案是否達(dá)標(biāo)通常只需要老老實實累加一遍。整個算法的骨頭就是兩根一根是有序的搜索空間一根是廉價的判定函數(shù)。判定函數(shù)寫得越干凈二分部分就越不容易出錯。2. 邊界、判定與整數(shù)二分的實操細(xì)節(jié)2.1 上下界怎么取直接決定迭代次數(shù)和溢出風(fēng)險搜索區(qū)間我一般取 lo 0hi max(h)。lo 取 0 是有講究的如果題目數(shù)據(jù)保證有解答案最小就是 0也就是把鋸子架在地面上所有樹全砍這是理論上的產(chǎn)出上限。lo 取 0 而不是取 1是為了讓樹高很矮、m 很小的數(shù)據(jù)不會漏掉正確答案 0——雖然多數(shù)版本保證 m ≤ 總產(chǎn)出但邊界留一手總沒壞處。hi 取 max(h) 而不是取一個大到離譜的常數(shù)比如 10^9理由有兩個。第一鋸子架得比最高的樹還高產(chǎn)出必定是 0那些區(qū)間全是無效迭代白白多跑幾次判定第二hi 取得過大某些寫法里的 mid 計算雖然不會溢出但會讓答案恰好等于 max(h)這種邊界情況下的收斂過程變得難以推理。提示能精確取到的上界一定要精確取別偷懶寫成 1e9。二分題的 hi 定錯等價于給答案挖了一個自己看不見的坑。2.2 check 函數(shù)里三個容易被忽略的寫法要點(diǎn)第一是提前退出。判定函數(shù)沒必要把所有樹都累加完一旦累加值已經(jīng)大等于 m立刻 return true。別小看這一句剪枝在實際數(shù)據(jù)里如果 m 很小而樹很多它能省下大量加法。第二是累加變量必須用 64 位整數(shù)。n 最大到 10^5、h_i 最大到 10^9 的時候總產(chǎn)出上限是 10^14早就超出了 32 位整數(shù)大約 2.1×10^9 的表達(dá)能力。老實說我自己在訓(xùn)練初期就在這類加一加就溢出的題上吃過不下五次的罰后來養(yǎng)成的習(xí)慣是只要題目里出現(xiàn)累加變量一律用 long long不糾結(jié)。第三是別做無意義的取模或開方。有些同學(xué)喜歡在判定里用 sqrt 或者對數(shù)提前估個大概二分題里完全不需要浮點(diǎn)誤差反而會把邊界搞亂。整數(shù)題就用整數(shù)算干凈利落。2.3 整數(shù)二分的三種常見模板與死循環(huán)陷阱整數(shù)二分的寫法五花八門但坑其實只有一個mid 的取整方向和邊界的收縮方向必須配套否則要么死循環(huán)要么答案差一。下面把我常用的三種寫法列出來對比。模板核心寫法適用場景死循環(huán)風(fēng)險閉區(qū)間 記錄答案while(lohi){mid(lohi)/2; if(ok) ansmid,lomid1; else himid-1;}求最大可行值最好懂低推薦新手閉區(qū)間收縮while(lohi){mid(lohi1)/2; if(ok) lomid; else himid-1;}求最大可行值代碼短高mid 忘記加一就死循環(huán)左閉右開while(lohi){mid(lohi)/2; if(ok) himid; else lomid1;}求最小可行值中邊界含義要記牢新手我強(qiáng)烈推薦第一種記錄答案法。它的好處是心理負(fù)擔(dān)極低只要 ok(mid) 成立就把 mid 記下來然后往更大的方向試不成立就往更小的方向試。區(qū)間一定會收縮因為兩邊都是 mid±1根本不可能死循環(huán)。代價只是多一個變量和一次賦值換來的是五分鐘就能寫完并且一次過。第二種寫法是很多模板文里的默認(rèn)寫法它的效率略微高一點(diǎn)點(diǎn)但mid (lo hi 1) / 2那個加一是命門。如果寫成mid (lo hi) / 2在 lo 和 hi 相鄰時 mid 會等于 lo而 ok 成立時lo mid又不動于是原地轉(zhuǎn)圈程序永遠(yuǎn)停不下來。這類死循環(huán)不會報錯只會讓你在提交頁面上看到 TLE然后一頭霧水地盯半天代碼。2.4 一個常被忽略的邊界全都砍不到怎么辦有一種邊界情況值得單獨(dú)說當(dāng)把所有樹全部砍倒H 0的總產(chǎn)出都小于 m 時判定函數(shù)在整個搜索區(qū)間上都返回 false。這時候記錄答案法里的 ans 會保持初始值輸出 0。這個結(jié)果在數(shù)學(xué)上是無解但在很多題面里會被保證不會出現(xiàn)。我建議的穩(wěn)妥做法是先讀入的時候順手把總高度加起來如果總高度小于 m按題目要求處理——要么輸出 0要么特殊判斷。多寫這三行能防住一整類神秘的錯誤答案。3. 代碼實現(xiàn)與完整實操流程3.1 C 版本一份可以直接抄的模板下面這份代碼是我平時訓(xùn)練時用的版本讀入用ios::sync_with_stdio(false)關(guān)同步累加用 long long二分用記錄答案法基本可以直接套到任何最大值可行的二分題上。#include bits/stdc.h using namespace std; int n; long long m; vectorlong 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; }幾個細(xì)節(jié)解釋一下。mid lo (hi - lo) / 2和(lo hi) / 2在 long long 范圍內(nèi)其實差不多但前者是更保險的寫法兩個大數(shù)相加不會溢出是個值得養(yǎng)成的習(xí)慣。total在輸入階段順帶統(tǒng)計用來做無解判斷幾乎零成本。提前剪枝那句if (sum m) return true;放在循環(huán)內(nèi)部而不是循環(huán)外是因為一旦夠了就沒必要繼續(xù)掃在 m 偏小的數(shù)據(jù)上能明顯提速。3.2 Python 版本排序加前綴和把判定壓到 O(log n)Python 寫這題要留個心眼如果判定函數(shù)是 O(n) 的線性掃描n 10^5、二分大約 30 輪就是 3×10^6 次加法用純 Python 循環(huán)跑通常能過但要一兩秒碰上更狠的數(shù)據(jù)就懸了。我的做法是提前排序并做前綴和把每次判定降到 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 的樹貢獻(xiàn)的總和等于所有樹高度之和減去高度不超過 H 的那些樹的高度之和再減去高于 H 的樹的數(shù)量乘以 H。前半部分用前綴和 O(1) 拿到樹的數(shù)量用二分查找 bisect_right 在 O(log n) 內(nèi)定位。整道題的總復(fù)雜度變成 O(n log n log(max h) × log n)在 Python 里基本是毫秒級的事情。3.3 復(fù)雜度賬數(shù)據(jù)規(guī)模對照表我一直覺得寫題時不先把復(fù)雜度賬算清楚等于閉著眼睛開車。下面這張表把暴力枚舉和二分答案在幾檔典型規(guī)模下的運(yùn)算量擺在一起差距一眼可見。數(shù)據(jù)規(guī)模暴力枚舉運(yùn)算量二分答案運(yùn)算量結(jié)論n 1000, h ≤ 1000約 10^6約 10^4暴力能過n 10^4, h ≤ 10^5約 10^9約 1.7×10^5暴力必掛n 10^5, h ≤ 10^9約 10^14約 3×10^6只能二分n 10^6, h ≤ 10^9完全不可能約 3×10^7二分 讀入優(yōu)化這里的 log 底數(shù)是 2因為每次判定把區(qū)間砍一半。log?(10^9) 大約是 30也就是說二分的迭代次數(shù)永遠(yuǎn)在 30 上下幾乎和數(shù)據(jù)范圍無關(guān)。這就是二分答案最迷人的地方搜索空間的絕對大小不重要重要的是它的對數(shù)規(guī)模。3.4 一次完整的實操流程記錄我在本地做這道題的習(xí)慣流程是這樣順序基本固定幾乎不會漏東西。第一步讀題并在紙上寫下不等式 Σ max(0, h_i ? H) ≥ m第二步驗證單調(diào)性寫一句話證明第三步定上下界lo 0hi max(h)第四步先寫判定函數(shù)并用手算樣例驗證第五步套二分模板第六步造三組數(shù)據(jù)樹高全相等、只有一棵樹、m 恰好等于總產(chǎn)出的一半跑一遍看結(jié)果合不合理第七步寫暴力對拍。這個順序的意義在于把設(shè)計和編碼分開。很多人一上來就敲代碼結(jié)果邊界錯、方向反、溢出全混在一起調(diào)起來極其痛苦。先把不等式和單調(diào)性寫在紙上等于給自己畫了張地圖后面出問題也能快速定位到底是哪一步錯了。4. 常見問題與排查實錄4.1 典型錯因速查表這是我這些年收集的、也是給學(xué)弟學(xué)妹講得最多的一張表。同一個錯誤反復(fù)出現(xiàn)說明它不是偶然而是思維上的慣性漏洞。提交現(xiàn)象根本原因修正方案運(yùn)行超時判定寫得沒問題二分死循環(huán)lo mid配向下取整用mid (lohi1)/2或改用記錄答案法答案比正確值小 1邊界收縮方向?qū)懛窗芽尚薪馀懦酥匦峦埔槐?ok 與 lo/hi 的對應(yīng)關(guān)系部分大數(shù)據(jù)答案離譜累加用了 int發(fā)生溢出累加變量統(tǒng)一改成 long long答案偏大上界 hi 取了 1e9浮點(diǎn)比較或越界hi 精確取 max(h)特定數(shù)據(jù)全錯忽略全砍完也不夠的邊界先判斷總高度與 m 的關(guān)系多組測試時第二組開始錯全局?jǐn)?shù)組沒清空每組數(shù)據(jù)重建容器表格里最值得說的是第一條。死循環(huán)是二分題的頭號殺手而且它不給你任何提示只會讓你對著屏幕發(fā)呆。我的判斷辦法很簡單只要代碼里出現(xiàn)了lo mid這種賦值不推進(jìn)的語句立刻條件反射地去檢查 mid 的取整是不是向上取整。4.2 對拍讓暴力程序給二分當(dāng)裁判對拍是排查二分邊界問題最有效的武器沒有之一。原理很樸素寫一個一定正確的暴力程序再寫一個隨機(jī)數(shù)據(jù)生成器循環(huán)跑幾百組比對兩個程序的輸出。只要有一組不一樣就把那組數(shù)據(jù)留下來手工分析。下面是 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], inputinp, capture_outputTrue, textTrue).stdout.strip() out2 str(brute(n, m, h)) if out1 ! out2: print(發(fā)現(xiàn)問題數(shù)據(jù)) print(inp) print(二分輸出, out1, 暴力輸出, out2) break else: print(500 組全部一致)跑對拍時有三個細(xì)節(jié)要注意。第一先用小數(shù)據(jù)n ≤ 8、h ≤ 20跑這樣萬一出錯你能手工驗算第二m 的取值范圍一定要先限定成必定有解把核心邏輯確認(rèn)無誤之后再放開邊界去測試無解的情況第三隨機(jī)數(shù)的種子最好固定一下方便復(fù)現(xiàn)不然偶發(fā)的錯誤數(shù)據(jù)丟了你得重新碰運(yùn)氣。4.3 手推一組樣例把抽象過程具象化看代碼之前先手推一組數(shù)據(jù)理解會牢固得多。設(shè)四棵樹高度分別是 20、15、10、17要求總木材不少于 7。H 15 的時候產(chǎn)出是 (20?15) (17?15) 5 2 7剛好夠。H 16 的時候產(chǎn)出是 4 1 5不夠。所以答案是 15。這組數(shù)據(jù)有意思的地方在于它正好卡在邊界上7 這個數(shù)字不偏不倚。我建議每個人在自己做題的時候都準(zhǔn)備兩組這種剛好卡住的樣例因為它能同時驗證兩件事可行值能取到且不可行值確實被排除了。如果你的代碼對 H 15 輸出 14 或者 16那基本可以確定是邊界收縮寫錯了直接去看模板那一節(jié)。4.4 讀入和常數(shù)優(yōu)化上的小經(jīng)驗最后分享幾個實戰(zhàn)里總結(jié)的小經(jīng)驗都是正規(guī)題解里很少寫、但能實實在在省下提交次數(shù)的東西。第一輸入量大的時候一定要關(guān)同步或者用快讀。C 里ios::sync_with_stdio(false); cin.tie(nullptr);這兩行我?guī)缀跏菞l件反射地寫上它帶來的提升在大數(shù)據(jù)下非常明顯。Python 里則要用sys.stdin.buffer.read().split()一次性讀完而不是一行一行input()。第二判定函數(shù)里的剪枝要放在循環(huán)體內(nèi)。很多同學(xué)把提前退出寫在累加完成之后等于白寫。真正有效的剪枝是在累加的過程中一旦達(dá)標(biāo)立刻返回。第三不要迷信基礎(chǔ)題這三個字。這道題的每一個知識點(diǎn)都不難但知識點(diǎn)多任何一環(huán)出錯都會導(dǎo)致整體失敗。把每個環(huán)節(jié)都在紙上寫清楚比反復(fù)重寫代碼高效得多。5. 變式與進(jìn)階拓展5.1 恰好等于版本的改法如果題面把條件改成總產(chǎn)出恰好等于 m思路稍微變一下。做法是先用同樣的二分找出滿足總產(chǎn)出 ≥ m 的最大 H記為 H*然后單獨(dú)算一次 check(H*) 對應(yīng)的實際總產(chǎn)出如果它正好等于 m就輸出 H*如果大于 m說明無論如何都湊不出恰好等于按題面要求輸出無解標(biāo)識。這里有個思維上的提醒二分能處理的永遠(yuǎn)是不等式形式的單調(diào)判定恰好等于這類等式約束需要在不等式結(jié)果的基礎(chǔ)上再補(bǔ)一次校驗。把這兩件事混在一起寫進(jìn)判定函數(shù)是新手很容易掉進(jìn)去的坑因為恰好等于關(guān)于 H 并不單調(diào)根本沒法二分。5.2 換個外殼切木頭與合并木頭同一個算法核心換一層題面就能變成另一道題。比如把砍樹換成把若干根原木切成等長的 k 段求每段的最大長度判定邏輯一模一樣給定長度 L算一算所有原木能切出多少段夠不夠 k。再比如把問題反過來要求把若干段木料合并成規(guī)定的段數(shù)使總代價最小那就不是二分答案了而是經(jīng)典的優(yōu)先隊列貪心每次取出最短的兩段合并。我經(jīng)常拿這一組題放在一起講目的就是讓讀者意識到題面是皮模型是骨?？吹娇澈颓邢葐栕约阂痪洹@是可行性單調(diào)的判定問題還是每一步都要做局部最優(yōu)決策的貪心問題分清楚這兩類選型就不會跑偏。5.3 多工人并行版本的一點(diǎn)思路還有一種常見變形場上不止一個伐木工每人只能在一個固定高度切一刀問怎么安排高度使得總產(chǎn)出達(dá)標(biāo)。這種題通常就不是單純的二分答案了需要先排序再貪心分配或者轉(zhuǎn)成二分答案加可行性貪心檢查的組合。組合類題目我個人的經(jīng)驗是先別急著上算法先把題目里的約束一條條列出來看清楚哪一條是單調(diào)的、哪一條是組合性的。單調(diào)的那部分用二分處理組合的那部分用排序或堆處理兩者拼起來往往就是標(biāo)算。硬套單一模板十有八九會在某組數(shù)據(jù)上翻車。5.4 從這道題沉淀下來的通用套路最后說點(diǎn)方法論層面的東西。這道題教會我的東西其實遠(yuǎn)遠(yuǎn)超出會寫二分這個層面。第一遇到最大值最小最小值最大滿足條件的最優(yōu)值先寫判定函數(shù)再想二分這個順序不能反。判定函數(shù)寫清楚了二分只是殼子。第二單調(diào)性一定要證明哪怕只是一句話。沒有單調(diào)性支撐的二分就是空中樓閣對拍再多次也救不了。第三邊界永遠(yuǎn)是最貴的地方。上下界的選取、mid 的取整方向、循環(huán)終止條件這三處我每次都會多看兩眼。經(jīng)驗告訴我絕大多數(shù)二分 WA 都死在這三處而不是死在算法思想上。第四也是最實在的一條所有涉及累加的變量先用最寬的整數(shù)類型等到確認(rèn)性能有問題再考慮降位。省下來的那點(diǎn)內(nèi)存根本抵不上一遍遍調(diào)試溢出的時間成本。這個習(xí)慣我從這道基礎(chǔ)題開始養(yǎng)成后來打各類比賽時救過我好幾次。順便提一句這道題如果數(shù)據(jù)范圍不大用排序加雙指針甚至可以直接算出答案但那就失去練習(xí)二分的意義了。既然是拿它當(dāng)練手題就老老實實按二分答案的完整流程走一遍把判定函數(shù)、邊界、對拍這三樣?xùn)|西完整地過一遍手。以后再遇到同類問題你會發(fā)現(xiàn)自己的第一反應(yīng)已經(jīng)變成先看單調(diào)性而不是先想暴力怎么優(yōu)化。