1. 從“河中跳房子”到二分答案一個經(jīng)典思維的誕生如果你剛開始接觸算法競賽或者刷題看到“1247河中跳房子”這個標題可能會覺得有點摸不著頭腦。這聽起來像是個游戲或者物理題怎么就成了經(jīng)典的算法例題我第一次遇到它時也有同樣的疑惑但真正動手做下來才發(fā)現(xiàn)這道題簡直是理解“二分答案”這個核心思想的絕佳敲門磚。它沒有復雜的圖論結構也沒有繁瑣的動態(tài)規(guī)劃狀態(tài)轉移就是用一個最樸素的場景逼著你去思考一個根本問題當答案本身難以直接求解但給定一個“候選答案”后我們能快速判斷它是否可行時我們該怎么辦“河中跳房子”描述的場景非常直觀有一條河河中間有N個石頭房子它們與起點的距離是已知的。現(xiàn)在我們要從起點跳到終點每次跳躍必須落在石頭上并且跳躍距離不能小于一個給定的值。問題是在必須移走恰好M塊石頭的情況下如何安排移走哪些石頭使得最終能夠完成跳躍的最短跳躍距離盡可能大這個“盡可能大的最短跳躍距離”就是我們要求解的答案。為什么這個問題適合用二分答案因為答案——那個最短跳躍距離——是一個整數(shù)并且存在一個明確的邊界。想象一下如果允許的跳躍距離非常小比如1那么你幾乎可以踩著所有石頭過去移走M塊石頭后肯定也能過去所以這個答案是“可行”的。如果允許的跳躍距離非常大大到超過相鄰石頭間的最大間隔那么你移走M塊石頭后必然存在一段你跳不過去的空隙所以這個答案是“不可行”的。于是在“可行”與“不可行”之間存在一個臨界點。我們的目標就是找到這個最大的、依然可行的跳躍距離。手動去猜這個數(shù)顯然效率低下而二分查找正是用來在有序范圍內(nèi)快速定位這種臨界點的利器。網(wǎng)絡上相關的熱詞如“二分答案”、“二分查找”、“貪心算法”都指向了這里。很多人學二分只記住了在有序數(shù)組里找某個數(shù)卻不知道“二分答案”才是二分思想更具威力的應用。這道題就是一個完美的橋梁它要求你跳出“在給定序列中查找”的定式思維轉而去在一個答案的可能區(qū)間里利用一個判斷函數(shù)來縮小區(qū)間。這個思維模式的轉換是解決一大批最優(yōu)化問題的關鍵從安排會議時間到分配資源其內(nèi)核都是相通的。2. 問題拆解定義、約束與核心挑戰(zhàn)在動手寫代碼之前我們必須把題目嚼碎了咽下去理解每一個條件背后的意圖。這不僅僅是讀懂題目更是為了設計出正確的“可行性判斷”函數(shù)這是二分答案的靈魂。2.1 問題要素的精確翻譯首先我們把生活化的描述翻譯成程序員熟悉的語言輸入河的長度L起點到終點的距離石頭數(shù)量N不包括起點和終點必須移走的石頭數(shù)M以及N塊石頭距離起點的位置升序給出。隱含點起點位置0和終點位置L是固定的不能移動。我們跳躍的“舞臺”就是由起點、終點以及剩下的 (N - M) 塊石頭構成的。動作從起點開始每次跳到下一塊剩余的石頭最終跳到終點。每次跳躍的距離就是兩塊石頭位置之差。目標在移走恰好M塊石頭后找出一種保留石頭的方案使得所有跳躍距離中的最小值最大。輸出這個最大的最小值。這里有一個非常關鍵的理解點我們不是要找出移走哪M塊石頭而是要找到一個最大的距離D使得存在一種移走M塊石頭的方法讓剩下的石頭包括起點終點中任意相鄰兩塊的距離都至少為D。前者是一個具體的組合方案后者是一個數(shù)值目標。二分答案幫我們找到的是后者。只要我們能判斷某個D是否可行我們就能用二分逼近最大的那個D。2.2 為什么貪心算法是可行性判斷的“最優(yōu)解”給定一個候選的“最短跳躍距離”D如何判斷在移走不超過M塊石頭的前提下能否實現(xiàn)所有跳躍距離都 D一個最直接的思路是模擬跳躍過程。我們從起點位置0開始看向下一塊石頭。如果當前石頭與下一塊石頭的距離 D那么我們可以安全地跳過去并把下一塊石頭作為新的起點。如果距離 D說明這塊石頭太近了如果我們不跳過去就無法到達終點因為我們必須按順序跳。那么唯一的辦法就是移走這塊距離太近的石頭然后繼續(xù)比較當前石頭與再下一塊石頭的距離。這個過程天然就是一個貪心算法我們在每一步都做出局部最優(yōu)選擇——只要石頭夠遠就跳過去不夠遠就移走它。為什么貪心在這里是正確的因為我們的目標是讓所有間隔 D并且希望移走的石頭盡可能少。如果當前石頭和下一塊石頭距離小于D保留下一塊石頭必然導致這段間隔不達標。移走它是為后續(xù)的間隔創(chuàng)造可能讓當前石頭直接對接更后面的石頭。這個決策只影響當前這一段不會對未來的決策產(chǎn)生后效性因此貪心是有效的。具體判斷函數(shù)check(D)的邏輯如下初始化last_pos 0起點位置removed 0移走石頭計數(shù)。遍歷每一塊石頭位置為stone[i]計算stone[i] - last_pos。如果距離 D說明石頭i太近必須移走removed。如果距離 D說明可以跳到石頭i更新last_pos stone[i]。遍歷結束后不要忘記終點計算L - last_pos最后一塊保留的石頭到終點的距離。如果這個距離也 D那么意味著即使調(diào)整石頭從最后一塊石頭也無法跳到終點這個D肯定不可行。實際上在貪心過程中如果最后一段距離小于D我們已無石頭可移終點不能移所以直接判定不可行。判斷removed M。如果成立說明用不超過M次的移除操作可以實現(xiàn)所有跳躍 DD是可行的否則不可行。注意這里有一個非常重要的細節(jié)也是容易出錯的地方。check(D)函數(shù)判斷的是“能否在移走不超過M塊石頭的情況下實現(xiàn)條件”。題目要求是“移走恰好M塊”那會不會有“移走少于M塊就能滿足條件導致我們找到的不是題目要求的解”的情況實際上如果某個D滿足“移走 M 塊石頭即可”那么它一定是可行的。因為我們可以通過額外移走一些無關緊要的石頭比如在已經(jīng)很遠的間隔中間再移走一塊湊足恰好M塊而這并不會降低已有的最短跳躍距離。所以check(D)的條件是寬松的這保證了二分過程的正確性。我們最終找到的是滿足“移走 M 塊石頭即可”的最大D它必然也對應著一種“移走恰好M塊石頭”的方案可以通過額外移除來湊數(shù)。3. 二分查找的邊界與循環(huán)設計避開死循環(huán)的坑理解了check(D)我們就有了在答案空間里導航的指南針。接下來我們需要確定搜索的起點和終點并設計一個永不迷路的二分循環(huán)。3.1 答案邊界的確定答案最短跳躍距離的最大值最小是多少理論上可以是0但0沒有實際意義且我們的判斷函數(shù)在D0時總是成立。更實際的下界是1。答案最大是多少一種樸素的認為是河的長度L但顯然不可能跳那么遠。一個更緊的上界是L本身如果你能一腳從起點跳到終點。但在二分時我們通常設置一個安全的、肯定不可行的上界。因為當D大于任意兩塊石頭包括起點終點之間的間隔時必然不可行。所以我們可以設置left 1,right L。為了確保完全覆蓋有時會設置right L 1這樣即使check(L)為真我們的二分區(qū)間也能容納它。在我的實踐中更推薦一種清晰且不易出錯的方式int left 1; // 最短跳躍距離至少為1 int right L; // 最長不會超過河的長度 // 或者考慮到如果所有石頭都移走最短距離就是L所以rightL是合理的。3.2 二分循環(huán)的“左閉右開”與“左開右閉”抉擇這是二分查找最容易寫出死循環(huán)的地方。關鍵在于明確你維護的區(qū)間含義。我們尋找的是最后一個滿足check(mid) true的D。假設我們維護的區(qū)間是[left, right]其中check(left)為真check(right)為假。我們的目標是不斷縮小這個區(qū)間直到left和right相鄰。我強烈推薦并使用“左閉右開”的寫法即區(qū)間表示為[left, right)。它的循環(huán)不變式是left指向一個可行的答案right指向一個不可行或未探索的邊界。最終當left 1 right時left就是我們要找的最大可行解。對應的循環(huán)模板如下while (left 1 right) { int mid left (right - left) / 2; // 防止溢出 if (check(mid)) { left mid; // mid可行說明答案至少是mid將左邊界推進到mid } else { right mid; // mid不可行說明答案必須小于mid將右邊界收縮到mid } } cout left endl; // 循環(huán)結束時left就是最大可行值這種寫法的好處非常明顯永不退循環(huán)條件left 1 right保證了區(qū)間內(nèi)至少有兩個元素時才需要循環(huán)。當區(qū)間縮小到[left, left1)時循環(huán)結束。更新清晰因為區(qū)間是右開的當mid可行時我們將left設為mid這很自然。當mid不可行時我們將right設為mid因為mid本身已經(jīng)不可行新的右邊界應該是它開區(qū)間不包含mid。答案明確循環(huán)結束后left就是最后一個被驗證可行的值直接輸出即可。對比常見的while (left right)寫法那種寫法需要處理mid的加減1并且最終答案的存儲變量是left還是right還是ans容易混淆?！白箝]右開”模板將答案的維護隱含在了區(qū)間邊界里邏輯更簡潔幾乎可以成為二分答案問題的標準寫法。3.3 一個完整的算法流程梳理讀入L, N, M以及石頭位置數(shù)組stones。為了方便處理可以在數(shù)組開頭插入0起點末尾插入L終點。定義check(int d)函數(shù)實現(xiàn)上述貪心邏輯返回布爾值。初始化二分邊界left 1,right L 1或right L但需確保check(L)為真時也能正確處理。執(zhí)行“左閉右開”的二分循環(huán)。輸出left。4. 代碼實現(xiàn)、測試與極端情況分析理論清晰之后我們來落地成代碼并思考一些邊界情況確保我們的解決方案是健壯的。4.1 完整的C代碼實現(xiàn)#include iostream #include vector #include algorithm using namespace std; int L, N, M; vectorint stones; // 判斷是否能在移走不超過M塊石頭的情況下使得最短跳躍距離至少為d bool check(int d) { int last_pos 0; // 起點位置 int removed 0; // 遍歷所有石頭 for (int i 0; i N; i) { if (stones[i] - last_pos d) { // 距離太近必須移走當前石頭 removed; if (removed M) { // 移走數(shù)量已超限提前返回false return false; } } else { // 可以跳過去更新上一個位置 last_pos stones[i]; } } // 檢查最后一塊保留的石頭到終點的距離 // 注意終點L已經(jīng)包含在stones數(shù)組末尾了嗎這里假設沒有。 // 更穩(wěn)妥的做法是將終點L也視為一塊“石頭”加入數(shù)組這樣循環(huán)內(nèi)就包含了終點判斷。 // 以下是未將終點加入數(shù)組時的判斷 if (L - last_pos d) { return false; // 最后一段跳不到終點 } return removed M; } int main() { cin L N M; stones.resize(N); for (int i 0; i N; i) { cin stones[i]; } // 為了方便可以對石頭位置排序題目雖說是升序給出但排序是個好習慣 sort(stones.begin(), stones.end()); // 二分查找 int left 1; int right L 1; // 右開區(qū)間L1是一個肯定不可行的值因為最大距離是L while (left 1 right) { int mid left (right - left) / 2; if (check(mid)) { left mid; // mid可行嘗試更大的 } else { right mid; // mid不可行縮小范圍 } } cout left endl; return 0; }代碼優(yōu)化點如注釋所述將終點L作為一塊“石頭”插入stones數(shù)組末尾可以使check函數(shù)邏輯更統(tǒng)一無需單獨判斷最后一段。修改如下stones.push_back(L); // 在輸入并排序后加入終點 N stones.size(); // 更新石頭數(shù)量包含了終點 // 修改check函數(shù)移除對 L - last_pos 的單獨判斷因為終點已在數(shù)組中。 bool check(int d) { int last_pos 0; int removed 0; for (int pos : stones) { // 現(xiàn)在stones包含了終點 if (pos - last_pos d) { removed; if (removed M) return false; } else { last_pos pos; } } return true; // 如果能遍歷完所有“石頭”包括終點說明成功到達 }4.2 極端情況與測試用例任何健壯的算法都需要考慮邊界。情況一M 0一塊石頭都不能移。此時問題退化為給定間隔求最小間隔的最大值實際上答案就是所有相鄰石頭包括起點終點間隔的最小值。我們的算法能工作嗎可以。check(D)函數(shù)會嘗試移走距離小于D的石頭但因為M0一旦需要移走就會返回false。二分會找到最大的那個D使得沒有任何間隔小于D即所有間隔都 D。這個D就是最小間隔。情況二M N所有石頭都可以移走。此時我們可以移走所有石頭直接從起點跳到終點。那么最大的最短跳躍距離就是河的長度L。我們的算法中check(L)會成功嗎在貪心過程中因為起點0到任何一塊石頭的距離都小于L除非石頭就在L所以所有石頭都會被標記為移走removed N滿足removed M。并且最后last_pos還是0終點L到0的距離等于L滿足條件。所以check(L)返回true。二分會找到L。情況三石頭位置有重復。題目通常保證位置互異但如果輸入有重復我們的算法依然有效。對于兩個位置相同的石頭它們之間的距離為0在任何D0的情況下第一塊都會被保留第二塊會被移走因為距離0 D。情況四L很小N很大。二分查找的復雜度是 O(logL * N)在常規(guī)數(shù)據(jù)范圍內(nèi)L10^9, N50000完全可行。4.3 與“最小值最大化”同類問題的對比“河中跳房子”是“最小值最大化”問題的典型代表。類似的還有“進擊的奶?！痹谝粭l數(shù)軸上放N個牛棚要放入C頭牛使得任意兩頭牛之間的最小距離最大。解法幾乎一模一樣check(d)函數(shù)判斷能否在保證牛之間距離至少為d的情況下放下所有牛?！翱硺洹庇蠳棵樹需要砍下M米長的木材鋸子的高度為H樹木高于H的部分會被砍下。求最大的H使得砍下的木材總長度至少為M。這里check(H)計算木材總長度是否 M?！胺峙漕A算”將總額為M的預算分配給N個項目每個項目有一個最低需求和最高需求求在滿足所有項目最低需求后能使獲得預算最少的那個項目得到的預算最大值。check(x)判斷能否在滿足每個項目至少獲得x預算的前提下分配完總預算。它們的共同模式是答案是一個數(shù)值其可行性與數(shù)值大小呈單調(diào)關系通常數(shù)值越大越難滿足條件并且存在一個判斷給定數(shù)值是否可行的函數(shù)。識別出這種模式就立刻可以套用二分答案的框架。5. 從二分答案到更廣闊的算法思維通過“河中跳房子”這個具體的例子我們深入演練了二分答案的完整流程。但這道題的價值不止于此它更像一個引子讓我們看到算法思維是如何層層遞進的。5.1 貪心與二分的結合112這道題的精妙之處在于它將貪心和二分完美結合。貪心算法負責在給定約束下的快速可行性判斷check函數(shù)其時間復雜度是O(N)。二分查找則負責在巨大的答案空間1到L中進行高效搜索時間復雜度是O(logL)。兩者結合總復雜度為O(N logL)輕松處理大規(guī)模數(shù)據(jù)。這種“二分外殼 貪心/其他算法內(nèi)核”的結構是解決許多最優(yōu)化問題的標準套路。關鍵在于你必須能夠寫出一個正確的、單調(diào)的check函數(shù)。5.2 調(diào)試二分當答案不對時怎么辦二分查找的bug往往難以察覺。如果你得到的答案不對可以按以下步驟排查驗證check函數(shù)這是最容易出錯的地方。構造幾個小例子手動模擬check(D)的過程特別是邊界情況D很小、D很大、M0、MN。確保你的貪心邏輯是正確的。驗證二分邊界打印出循環(huán)過程中l(wèi)eft,right,mid和check(mid)的值。觀察區(qū)間是否在正確收斂。確保你的初始right設置得足夠大是一個肯定不可行的值。驗證循環(huán)條件確認你的循環(huán)最終會停止。對于“左閉右開”模板while (left 1 right)是安全的。驗證最終答案循環(huán)結束后輸出的是left還是right根據(jù)你的區(qū)間定義來確認。在我們的模板里輸出left。5.3 舉一反三識別二分答案的適用場景在以后的刷題或工作中如何判斷一個問題是否能用二分答案解決問自己三個問題問題的答案是一個數(shù)值嗎通常是最大或最小的某個指標。如果我猜一個答案我能相對容易地判斷它是否“可行”嗎即能寫出check函數(shù)?？尚行院蛿?shù)值大小之間是否存在單調(diào)性例如對于“最小值最大化”問題數(shù)值越大越難滿足對于“最大值最小化”問題數(shù)值越小越難滿足。如果這三個問題的答案都是“是”那么二分答案就很可能是一個高效的解決方案。它把求解最優(yōu)值的問題轉化為了若干個判定性問題極大地簡化了思維難度?；剡^頭看“1247河中跳房子”它之所以經(jīng)典就是因為它干凈利落地呈現(xiàn)了這個思維范式。沒有多余的干擾直指核心。吃透這道題你收獲的不僅僅是一個AC的代碼更是一種面對復雜最優(yōu)化問題時化繁為簡、分而治之的強大武器。下次再遇到“最大的最小”、“最小的最大”這類字眼你會條件反射般地想到也許可以試試二分答案。