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