你看到“砍樹”這道二分答案題第一反應(yīng)是不是“這有什么好講的不就是套個二分模板”但說真的我見過太多人在 P1873 上栽跟頭——有二分邊界寫錯的有死循環(huán)跳不出來的有樣例過了結(jié)果 WA 到懷疑人生的。問題不在于你知不知道二分而在于你對“二分答案”這個套路有沒有形成肌肉記憶。今天我就拿這道洛谷 P1873 砍樹題當(dāng)靶子把二分答案從思路到代碼、從邊界到調(diào)試完整拆一遍。這篇文章適合剛學(xué)完二分查找、準(zhǔn)備進階二分答案的初學(xué)者也適合想系統(tǒng)梳理套路的中學(xué)生競賽選手當(dāng)然你如果是大學(xué)生期末復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)看到這篇也能少走不少彎路。1. 題目到底在說什么先讀懂砍樹的數(shù)學(xué)模型1.1 從一個生活場景說起伐木工人米爾科有一臺鋸木機他可以把鋸子的高度設(shè)成一個整數(shù) H機器從左到右掃過每一棵樹凡是高度大于 H 的樹高出 H 的那一截就會被鋸下來變成木材如果樹的高度本身小于等于 H那這棵樹就一根木頭都貢獻(xiàn)不出來。米爾科想要收集至少 M 米長的木材但他同時又希望 H 設(shè)得越高越好——因為 H 越高被砍到的樹越少森林看起來越“環(huán)?！倍掖蟛糠智闆r下鋸起來也省事。題目會給你 N 棵樹的實際高度讓你算出來這個最高能設(shè)到多少的 H。這個場景轉(zhuǎn)成數(shù)學(xué)語言其實特別簡單給你一個數(shù)組 a[1..N]你需要找一個最大的整數(shù) H使得所有 a[i] 中大于 H 的部分“切下來”之和 M。切下來的量就是 max(0, a[i] - H)對這 N 個數(shù)求和得到總木材量。1.2 第一反應(yīng)不能是暴力枚舉我第一次做這道題的時候腦子里第一個蹦出來的想法是那我把 H 從高往低一個一個試不就行了每試一個 H遍歷一遍所有樹算一算總木材量夠不夠夠的話就直接輸出。這個思路完全正確但它有一個致命問題復(fù)雜度。假設(shè)樹木高度的上限是 10^9你從最高往下每次減 1最多可能要枚舉 10^9 次每次又要遍歷 N 棵樹N 最大也有 10^6總操作量是 10^15 這個量級在任何競賽環(huán)境下都是直接超時?，F(xiàn)實生活里你也許不會覺得“從 10 億往下數(shù)到某個數(shù)”有多久但計算機面對這種數(shù)量級運算次數(shù)輕松突破一秒限制的幾百倍。所以這里必須換思路——不能一個一個試要一批一批地淘汰。1.3 二分答案本質(zhì)上就是猜答案二分查找大家都熟悉在有序數(shù)組里找一個目標(biāo)值每次砍掉一半。二分答案是把這套“砍半”的邏輯用在了一個更高層的維度上我們不是在一堆現(xiàn)成的數(shù)值里找一個存在的數(shù)而是在一個可能的答案區(qū)間里不斷猜測“什么樣的答案可行”。放到砍樹這道題里答案 H 一定落在某個范圍內(nèi)這個范圍我們有明確認(rèn)知最低是 0不砍任何樹當(dāng)然木材為 0最高不會超過所有樹中的最大值 maxH。如果 H 取 0肯定能滿足 M除非 M 是 0但題目 M 1如果 H 取 maxH那所有樹都砍不到東西木材為 0大概率不滿足。所以真正的答案卡在 0 和 maxH 之間。二分答案的精髓就是取中間值 mid (l r) / 2先假裝 H mid檢查一下這個高度下的木材總量夠不夠 M。如果夠說明 mid 這個高度是“可行”的那答案至少是 mid我們可以把區(qū)間左邊界往上提如果不夠說明 mid 太高了砍不到足夠的木頭那就把右邊界往下降。每判斷一次可用的答案范圍就縮小一半從 0 到 10^9 的范圍只需要大約 30 次判斷哪怕每次判斷要掃描一遍 N10^6 的數(shù)組總計算量也就是 3000 萬級別輕松跑完。2. 二分答案的套路拆解為什么它能工作2.1 單調(diào)性是整個二分的前提很多人背下了二分模板卻不知道模板之所以能用的底層原因。二分答案能成立的根基是“答案”和“可行性”之間存在單調(diào)關(guān)系。在這道題里單調(diào)性體現(xiàn)在H 越低能切下來的木材總量就越多H 越高木材總量就越少。換句話說木材總量是隨著 H 的增大而單調(diào)不增的函數(shù)。于是“是否滿足木材 M”這個判斷在整個答案區(qū)間里呈現(xiàn)出一種特殊的性質(zhì)——足夠小的 H 都是可行的足夠大的 H 都是不可行的中間存在一個分界線分界線上的臨界值就是我們要求的最大可行 H。單調(diào)性保證了我們可以反復(fù)二分因為每次判斷完 mid 之后一定能確定至少一半的區(qū)間里“所有值都可行”或者“所有值都不可行”從而把范圍安全地丟掉一半。如果題目缺少這種單調(diào)性二分答案就不成立。2.2 二分答案和二分查找的細(xì)微差別普通二分查找是在一個“有序數(shù)組”里查某個確定的值比較的是 a[mid] 和 target。二分答案則沒有所謂的“目標(biāo)值”可以直接比它比較的是“用 mid 作為參數(shù)去執(zhí)行一個判斷函數(shù)通常叫 check(mid)”的返回值判斷的是 mid 這個候選答案是否滿足約束條件。所以二分答案的模板里核心永遠(yuǎn)圍繞三個問題左邊界 l 代表什么右邊界 r 代表什么check(mid) 為真時應(yīng)該縮小哪一邊。很多初學(xué)者把跳轉(zhuǎn)邏輯寫反根源正是因為腦子里還在想“找某個數(shù)”而不是“判斷可行”。我建議你把二分答案直接理解成維護一個包含所有可行答案的大區(qū)間不斷把區(qū)間中確定不可行的一半丟掉最后收斂到邊界值。變量 l 要么表示“當(dāng)前已知的可行最大值”要么表示“左開右閉區(qū)間中的開邊界”不同寫法語義不同。2.3 check 函數(shù)的編寫思路寫二分答案題最重要、也最需要細(xì)心的是 check 函數(shù)。它決定了每次二分迭代時的判斷結(jié)果是否可靠。check 函數(shù)的邏輯在砍樹這道題里就一行遍歷所有樹累加 max(0, a[i] - H)如果累加結(jié)果大于等于 M返回 true否則返回 false。這里有一個隱藏考點累加值可能會非常大。N 最多 10^6每棵樹高度最大 10^9當(dāng) H 0 時總木材量可以達(dá)到 10^15。這個值遠(yuǎn)超 int 的表示范圍所以你在 check 函數(shù)里必須用 long long 類型累加否則直接溢出變成負(fù)數(shù)明明夠的木材被判成不夠二分結(jié)果就偏了。順便說一句有些人的 check 函數(shù)會“剪枝”一旦累加值已經(jīng)超過 M就直接返回 true不用繼續(xù)遍歷。這個優(yōu)化在 N 特別大、M 比較小的時候收益明顯因為實在沒必要把整片森林都掃完才知道夠不夠。代碼上寫起來就是循環(huán)里加一句 if (sum m) return true;。3. 完整代碼實現(xiàn)與關(guān)鍵細(xì)節(jié)3.1 一份可以直接抄作業(yè)的 C 實現(xiàn)先給結(jié)論這個是我自己用著最順手的寫法左閉右閉版本不容易迷路#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 是否可行。如果可行記錄當(dāng)前 mid 作為候選答案然后去更高的區(qū)間繼續(xù)嘗試如果不可行說明 mid 太高只能往更低的區(qū)間找。3.2 為什么初始區(qū)間設(shè)為 0 到 maxH先說下界為什么是 0。題目里 H 是鋸子的高度H 只能是非負(fù)整數(shù)低于 0 沒有實際意義。而且 H 取 0 時所有高于 0 的樹都會被完整砍倒木材量肯定是最大值一定滿足 M 1 的要求所以 0 一定可行。再說上界為什么是 maxH。如果 H 大于等于森林中最高樹的高度那么沒有任何樹能貢獻(xiàn)木材sum 恒為 0絕對不滿足 M 1。所以答案不可能超過 maxH。把區(qū)間直接卡到 [0, maxH]二分次數(shù)最多也就是 log2(10^9) 約 30 次而且一開始就排除了大量無效區(qū)域。有人問上界設(shè)成 0 和 maxH那會不會漏掉答案恰好是 maxH 的情況不會因為這棵樹即使是最高那棵只要 H maxH它自己剛好不高于 H不存在“高于 H”的部分所以確實砍不到木頭。答案要想等于 maxH必須 M 0但 M 至少是 1所以答案必然小于 maxH。不過代碼里用 ans 記錄當(dāng)前可行值所以即使二分在取等細(xì)節(jié)上有差異只要 check 寫得對就不會錯。3.3 死循環(huán)是怎么造成的邊界移動的學(xué)問二分最容易出bug的就是死循環(huán)。我見過不少人用整數(shù)二分時在某個特殊區(qū)間里反復(fù)橫跳永遠(yuǎn)收斂不了。死循環(huán)多半源于兩個極端一個是 mid 計算和邊界移動不一致。比如 l mid 但 mid 又不可能等于 l 的時候區(qū)間長度不變循環(huán)出不來。另一個是使用 l r 作為循環(huán)條件同時又用了 l mid 這種更新方式當(dāng) r - l 1 時mid 算出來就是 lcheck(l) 如果為真l 還是 l永遠(yuǎn)循環(huán)。我的建議是新手直接使用左閉右閉寫法配上 l mid 1 和 r mid - 1循環(huán)條件寫 l r并用 ans 單獨記錄可行答案。這種寫法邏輯最清晰幾乎見不到死循環(huán)問題。如果你非要用 l r 配 l mid 的寫法那記得 mid 要寫成 (l r 1) / 2向上取整防止區(qū)間無法縮小。3.4 數(shù)據(jù)規(guī)模與輸入輸出的隱藏陷阱這道題 N 是 10^6 級別如果用 cin 不關(guān)同步C 的輸入可能會吃不少時間。我在代碼里加了 ios::sync_with_stdio(false) 和 cin.tie(0)實測能明顯提速。另外數(shù)組開多大也很關(guān)鍵。題目說 N 最大 10^6我習(xí)慣多開一點點空間防止訪問越界聲明的 a 是 1e65 的 long long 數(shù)組足夠用了。最后強調(diào)一遍所有跟高度、木材總量相關(guān)的變量都要用 long long。你可能會說“樹高不是最多 10^9 嗎int 也能存啊”但問題出在中間計算 sum 上多個 10^9 加起來就會超過 2^31 - 1。所以防患于未然直接全部 long long一勞永逸。4. 常見錯誤與排查技巧實錄4.1 樣例過了但提交 WA先打印中間過程“樣例過了一交就WA”幾乎是所有二分題新手最痛的體驗。其實樣例只能證明你的代碼在某個特定數(shù)據(jù)下邏輯通順不能證明邊界處理正確。我調(diào)試砍樹題的慣用手段是如果 WA就在二分循環(huán)里臨時加輸出打印 l、r、mid、check(mid) 的返回值跑幾組小數(shù)據(jù)人工驗證一下區(qū)間收縮方向。比如手動構(gòu)造 N3, M10, 樹高為 [20, 15, 10] 的例子。check(10) 10 可行check(11) 9 不可行正確答案就是 10。如果你打印出來的 l、r 移動符合預(yù)期說明思路沒錯那就重點檢查 check 函數(shù)里有沒有漏判比如邊界條件多寫了一個等號。4.2 一個典型的錯誤check 里用了 int 導(dǎo)致誤判我有個模擬項目里用過這段錯誤代碼在這里分享給你避坑。當(dāng)時 N 不大樹高也小樣例全過但大數(shù)據(jù)一測試答案偏小。排查半天發(fā)現(xiàn)是 check 函數(shù)里 sum 用了 int。當(dāng) M 比較小的時候check 提前返回 true還沒溢出所以小數(shù)據(jù)集看著沒問題一旦 M 很大需要讀完整片森林sum 超過 int 上限直接變成負(fù)數(shù)后續(xù)比較 sum m 永遠(yuǎn)為假導(dǎo)致二分區(qū)間整體往低處偏移最終答案偏小。這種問題肉眼很難看出來所以我后來給自己定了一條規(guī)矩凡是可能累加超過 2^31 的量一律用 long long不用等到出問題再回頭改。4.3 死循環(huán)的現(xiàn)場還原與修復(fù)再分享一個死循環(huán)的經(jīng)典現(xiàn)場。假設(shè)代碼寫成這樣while (l r) { int mid (l r) / 2; if (check(mid)) l mid; else r mid - 1; }當(dāng) check(mid) 為真且 l r - 1 時mid l更新后 l 還是 l區(qū)間沒有變小循環(huán)出不來。這就是純粹因為更新邊界和二分形式不匹配導(dǎo)致的死循環(huán)。修復(fù)方式有兩種一種是改成我上面推薦的 l r 寫法另一種是保留 l r但把 mid 改成 (l r 1) / 2也就是向上取整。為什么向上取整因為當(dāng) l 需要保留為 mid 時向上取整才能讓 l 在必要時大于原來的 l從而保證區(qū)間一定縮小。4.4 常見問題速查表癥狀可能原因解決辦法死循環(huán)mid 取整方向與邊界更新方式不匹配統(tǒng)一為 lr 配 mid(lr)/2或用 lr 配 mid(lr1)/2答案偏小check 中 sum 溢出將 sum、H、樹高都改為 long long答案偏大循環(huán)條件錯誤多更新了一步檢查 r mid - 1 是否正確檢查 ans 是否只在 check 成功時更新超時cin 未關(guān)同步流使用 ios::sync_with_stdio(false); cin.tie(0);初值錯誤上界設(shè)成題目給的最大高度而非樹的最大高度輸入時記錄 maxH 作為右邊界4.5 邊界測試數(shù)據(jù)怎么構(gòu)造二分題目最容易出事的就是邊界附近。我給你幾個我經(jīng)常用來驗證的構(gòu)造思路所有樹一樣高比如 [5, 5, 5]需要木材為 1正確答案就是 4。只有一棵樹N1樹高 1需要木材 1正確答案是 0。樹高差距極大比如 [1000000000, 1]需要木材 1正確答案是 999999999。所需木材剛好是某個高度下的一部分檢驗取等邏輯。每次把這些邊界數(shù)據(jù)跑一遍如果你代碼都能正確輸出那基本上離 AC 就不遠(yuǎn)了。5. 二分答案的進階視角從砍樹題擴展到一類題5.1 不只是砍樹二分答案題的通用建模方法砍樹題是二分答案最經(jīng)典的入門題但它的價值遠(yuǎn)遠(yuǎn)不止“會做這一題”。我前面反復(fù)強調(diào)的“答案單調(diào)性”和“check 函數(shù)判斷可行性”可以遷移到大量題目里比如在一條直線上放置信號塔求最小覆蓋半徑比如把若干本書分給若干個人求某個人分到的頁數(shù)最大值的最小值比如猜數(shù)字游戲里用最少的次數(shù)鎖定某個整數(shù)。它們的共性是要求一個最值且這個最值具有“可行/不可行”的分界性質(zhì)。面對這類題我建議你按固定步驟思考先確定二分什么再思考這個量增大時約束是否具有單調(diào)性接著寫 check 函數(shù)判斷給定量是否可行最后根據(jù) check 結(jié)果收縮區(qū)間。這個四步法我用了很多年基本可以解決所有二分答案類問題。5.2 時間復(fù)雜度到底怎么算二分答案算法的復(fù)雜度是 O(N log V)其中 V 是答案值域的大小?？硺漕}的值域是 10^9log2(10^9) 約等于 30所以實際計算量是 N 乘以 30。N 最大 10^6總計算量 3000 萬在 C 下一般不會超過 1 秒。很多初學(xué)者會糾結(jié)這個復(fù)雜度會不會超你可以直接用經(jīng)驗判斷10^7 級別的計算在 1 秒內(nèi)沒問題10^8 級別要看常數(shù)和評測機10^9 基本危險。3000 萬屬于安全范圍。如果你用我代碼里的提前剪枝優(yōu)化實際遍歷次數(shù)通常會比 N 少尤其是 M 較小的時候速度會更快。所以我在寫二分答案題時check 里只要能提前終止就盡量提前終止。5.3 我的幾點實操體會做了很多二分答案題之后我的體會是二分答案難的不是二分本身而是 check 函數(shù)和邊界設(shè)計。每次交題前我至少會檢查三件事第一所有可能累加的數(shù)據(jù)類型是否足夠?qū)挼诙吔绺潞蛥^(qū)間形式是否匹配會不會產(chǎn)生死循環(huán)第三有沒有考慮空木材、恰好滿足 M 這類邊界條件。另外我強烈建議初學(xué)者不要背模板而是每次做題時把 l、r 的含義寫在注釋里。比如在代碼里寫清楚“l(fā) 表示當(dāng)前已知可行的高度”你就會發(fā)現(xiàn)二分方向永遠(yuǎn)不會搞反。我見過太多同學(xué)對著模板硬套一換題就懵根源就是沒有理解邊界變量的語義。提示如果你剛開始刷二分答案題建議把這道砍樹題當(dāng)作“模板題”反復(fù)手寫 3 遍不要看任何資料。等你能夠不假思索地寫出正確代碼再去做其他二分答案題你會發(fā)現(xiàn)所謂的新題只是換了一層場景外殼內(nèi)核還是那個二分。最后再分享一個我自己調(diào)試時常用的小技巧如果答案區(qū)間很大想快速驗證二分方向是否正確可以直接用二分中間值打印 check 的返回值再手動算一組小數(shù)據(jù)比較。比如樹高 [20, 15, 10]M10mid10 時 check 為 truemid14 時 check 為 11也 truemid15 時 check 為 5false?？吹竭@個走向你就知道答案落在 10 到 14 之間二分收縮方向完全正確。這個習(xí)慣幫我省下了大量定位 bug 的時間。