筆試結(jié)束那天晚上我在群里看到好幾個人發(fā)同一道題多多的擴容計劃。有人說自己寫了100多行的動態(tài)規(guī)劃有人用二分答案套貪心還有人樣例過了但心里沒底。其實這道題只要看穿一個關(guān)鍵性質(zhì)代碼只有十來行而且三種語言寫法幾乎一模一樣。如果你正在準(zhǔn)備大廠春招或者想練一練貪心證明這種筆試思維這篇復(fù)盤值得花幾分鐘看完。我先說結(jié)論這道題把所有擴容操作都放到第一天開始前一定是最優(yōu)的之后的問題就變成初始容量要多大才能吃下總消耗答案是總需求和的ceil(log2)。下面我把整個推導(dǎo)過程、三份參考代碼、在線測試時的輸入輸出細節(jié)和常見坑位都拆開講。1. 題目模型先把題面抽象成水池模型1.1 考場上拿到的題面我按記憶把原題復(fù)述成一個標(biāo)準(zhǔn) OJ 形式方便后面討論。多多有一臺初始容量為 1 的服務(wù)器接下來 N 天第 i 天業(yè)務(wù)會產(chǎn)生 a_i 的負載服務(wù)器當(dāng)天必須把負載全部處理完。處理完的負載會消耗掉對應(yīng)容量容量不會自動恢復(fù)。每天業(yè)務(wù)開始前多多可以花 1 金幣做一次擴容每次擴容讓當(dāng)前容量翻倍。擴容可以執(zhí)行任意次容量是永久提升的問最少花多少金幣才能保證所有天都不爆容量。輸入格式是兩行第一行一個整數(shù) N第二行 N 個整數(shù) a_1 到 a_N。輸出一行一個整數(shù)表示最少金幣數(shù)。約束方面N 最大可以到 10 萬a_i 最大可以到 10 的 9 次方所以總和會超過 32 位整數(shù)范圍這一點后面會專門說。給一個標(biāo)準(zhǔn)樣例輸入5 3 2 4 5 1輸出是4。這 5 天的總需求是 151 擴容 4 次后變成 16初始容量 16 已經(jīng)大于總需求 15所以 4 次就夠。模擬一下第 1 天消耗 3 剩 13第 2 天消耗 2 剩 11第 3 天消耗 4 剩 7第 4 天消耗 5 剩 2第 5 天消耗 1 剩 1全程不會爆容量。1.2 這題的關(guān)鍵是消耗而不是峰值很多人會第一眼把它看成容量峰值題只要服務(wù)器容量一直大于等于所有 a_i 的最大值不就行了這個想法只適用于容量不會因為處理任務(wù)而減少的版本。如果容量會被消耗情況就完全不同。舉個例子輸入[6, 6]。只看單日峰值 6初始擴容 3 次到 8 似乎就夠了因為ceil(log2(6)) 3。但第一天消耗 6 之后剩余容量只有 2第二天還要消耗 6明顯不夠。實際需要初始擴到 16也就是 4 次擴容。所以峰值視角會讓你漏掉前一天消耗之后后一天可能不夠用這種關(guān)鍵時間點。理解到這里后面推導(dǎo)就順了。1.3 按天模擬為什么能過樣例卻可能不是最優(yōu)我猜不少人考場上的第一反應(yīng)是寫一個按天模擬的貪心當(dāng)前容量不夠當(dāng)天的 a_i就不斷擴容直到夠用然后current - a_i把擴容次數(shù)累加。這個方案能跑出一個可行結(jié)果甚至能過不少樣例但它不是全局最優(yōu)。拿[5, 20]來試。按天模擬第 1 天開始時容量是 1要處理 5需要擴到 8做了 3 次擴容剩 3。第 2 天要處理 20當(dāng)前 3 不夠從 3 翻倍到 6、12、24又做 3 次擴容一共 6 次。但全局最優(yōu)只要 5 次第一天開始前直接把容量擴到 32做 5 次擴容第一天消耗 5 剩 27第二天消耗 20 剩 7全程足夠。為什么按天模擬會輸因為它總是在不夠了才擴這時候容量基數(shù)是小了的如果提前擴容翻倍的基數(shù)更大同樣的擴容次數(shù)能帶來更多容量。接下來我用一個嚴格的交換論證把這個直覺變成結(jié)論。2. 核心結(jié)論擴容全部提前一定不虧2.1 一個交換論證所有擴容都可以挪到第一天設(shè)任意一個可行的擴容方案總共有 K 次擴容。我們可以證明一定存在另一個仍然可行、而且不會花更多金幣的方案它讓這 K 次擴容全部發(fā)生在第一天開始前。理由是這樣的無論擴容發(fā)生在哪一天每次擴容都是把當(dāng)時的容量翻倍。如果某次擴容發(fā)生在第 j 天那么在那一天開始前服務(wù)器已經(jīng)消耗掉前 j-1 天的負載容量是某個值 C。如果把這同一次擴容挪到第一天開始前當(dāng)時還沒有任何消耗容量不小于 C翻倍之后得到的容量也一定不小于原來那次擴容之后得到的容量。把一次擴容提前只會讓之后每一天的可用容量變多不會讓任何一天變差。反復(fù)應(yīng)用這個調(diào)整所有擴容都能一步步挪到第一天而每天開始前的容量只會變大。最終我們得到一個容量曲線第一分鐘就把容量從 1 翻倍 K 次到 2^K之后再不擴容每天只消耗不增加。更簡潔地說一個總共 K 次擴容的方案在任何時刻的容量都不可能超過全部擴容提前到第一天的 2^K 減去已經(jīng)消耗的總量。因為后者相當(dāng)于把 K 次翻倍全部作用在了最大基數(shù)的初始容量上。所以最優(yōu)方案一定可以寫成第一天擴滿 K 次之后純消耗這種簡單形式。2.2 充要條件初始容量覆蓋總需求即可一旦確定所有擴容都放在第一天問題就變成了一個非常干凈的條件。設(shè)總共擴容 K 次初始容量就是 2^K。用 S_i 表示前 i 天的負載總和也就是前綴和。第 i 天開始前服務(wù)器剩余容量是 2^K 減去 S_(i-1)因為只有前 i-1 天消耗過容量。第 i 天能正常處理完的條件就是2^K - S_(i-1) a_i把 a_i 移到右邊等價于2^K S_(i-1) a_i S_i這個式子要對每一個 i 都成立。由于 a_i 都是正整數(shù)前綴和 S_i 是單調(diào)不減的所以最大的 S_i 就是最后一天結(jié)束后的總消耗SUM a_1 ... a_N。于是條件變成只要2^K SUM就行其他中間天自然都能滿足。反過來如果2^K SUM那么所有負載的總?cè)萘慷冀硬蛔∽詈笠惶熘耙欢ù嬖谀硞€時刻爆容量。因此充要條件就是初始容量不小于總需求答案就是最小的 K 滿足2^K SUM也就是ceil(log2(SUM))。這個結(jié)論也解釋了一個容易踩的誤區(qū)不要去管某一天的需求波動有多大也不用做任何剩余容量會不會不夠的判斷只需要把所有數(shù)字加起來然后看 2 的多少次方能蓋住這個總和。2.3 幾個直覺測試為什么看總需求是對的我給自己編了幾個例子用來快速驗證結(jié)論是不是真的合理。第一個例子是[60, 50]?？傂枨?1102^664 不夠2^7128 夠答案 7。模擬一遍初始 128第一天消耗 60 剩 68第二天消耗 50 剩 18安全。第二個例子是[100, 70, 70, 70]?？傂枨?3102^8256 不夠2^9512 夠答案 9。第一天消耗 100 剩 412后面三天各消耗 70完全沒問題。如果只看單日最大需求 100會得到 7但那是不對的因為 128 在第一天的剩余容量只有 28第二天的 70 都扛不住。第三個例子是[1,1,1,1,1,1]?？傂枨?62^24 不夠2^38 夠答案 3。雖然每一天需求都只有 1但六天累計還是要擴到 8 才穩(wěn)妥。這個例子特別適合拿去反駁只看最大值的思路。2.4 寫代碼前的兩個精度提醒計算ceil(log2(SUM))時不要直接用Math.log或者log函數(shù)取對數(shù)再向上取整。當(dāng) SUM 很大的時候浮點數(shù)計算會出現(xiàn)精度誤差尤其是 SUM 剛好落在 2 的冪次邊界附近誤差可能導(dǎo)致答案差 1。筆試環(huán)境里最穩(wěn)妥的做法是循環(huán)倍增用一個cap 1的變量不斷左移直到cap SUM左移次數(shù)就是答案。這樣既沒有浮點誤差代碼也直觀。另一個提醒是數(shù)據(jù)類型。N 最大 10 萬a_i 最大 1e9總和最大可以到 1e14。Java 里要用longC 里要用long longPython 無所謂但要注意讀入方式。如果你在 Java 里用了int總和直接溢出答案會變成負數(shù)或者完全錯誤這是筆試里最容易出現(xiàn)也最難受的失誤。3. Java / C / Python 三份參考實現(xiàn)3.1 Java 實現(xiàn)import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); StringTokenizer st new StringTokenizer(br.readLine()); long sum 0; for (int i 0; i n; i) { sum Long.parseLong(st.nextToken()); } long ans 0; long cap 1; while (cap sum) { cap 1; ans; } System.out.println(ans); } }Java 這邊有個細節(jié)不要用Scanner。N 到 10 萬時 Scanner 還能撐住但nextLong()在數(shù)據(jù)量大的時候會比較慢而且BufferedReader的寫法也不復(fù)雜筆試時直接用更穩(wěn)妥。注意讀第二行時用StringTokenizer分割避免字符串?dāng)?shù)組占用多余空間。3.2 C 實現(xiàn)#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long sum 0; for (int i 0; i n; i) { long long x; cin x; sum x; } long long ans 0; long long cap 1; while (cap sum) { cap 1; ans; } cout ans \n; return 0; }C 的老問題是cin默認和stdio同步讀大輸入時偏慢所以加上ios::sync_with_stdio(false)和cin.tie(nullptr)這行加速。變量一定要用long long如果圖省事寫int1e14的量級直接爆。左移cap 1在long long下完全安全因為ans最多幾十次不會溢出。3.3 Python 實現(xiàn)import sys def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) total 0 for i in range(1, n 1): total int(data[i]) ans 0 cap 1 while cap total: cap 1 ans 1 print(ans) if __name__ __main__: main()Python 這里用sys.stdin.buffer.read().split()一次性讀入所有 token比input().split()快很多尤其是數(shù)據(jù)量大的時候。int(data[i])直接轉(zhuǎn)換Python 的整數(shù)沒有位數(shù)上限所以不用擔(dān)心總和溢出。如果擔(dān)心read()占內(nèi)存也可以改用sys.stdin.readline()逐行讀但筆試場景下read()更方便。3.4 三份代碼的對比與時間復(fù)雜度語言核心注意點時間復(fù)雜度空間復(fù)雜度JavaBufferedReader longO(N)O(1) 額外空間Clong long ios 加速O(N)O(1) 額外空間Pythonsys.stdin.buffer.readO(N)O(N) 讀入數(shù)據(jù)或逐行讀 O(1)三種寫法本質(zhì)上是同一套邏輯先累加總和再循環(huán)算 2 的冪次數(shù)。時間復(fù)雜度都是 O(N)空間上除了輸入緩沖之外都是常數(shù)級。N 到 10 萬時這個復(fù)雜度非常寬裕跑起來沒有任何壓力。這道題真正的分水嶺不是算法復(fù)雜度而是能不能想到全部提前擴容這一步。4. 在線測試平臺怎么提交怎么自測4.1 OJ 提交時的輸入輸出細節(jié)在線測試平臺通常要求從標(biāo)準(zhǔn)輸入讀數(shù)據(jù)把結(jié)果打印到標(biāo)準(zhǔn)輸出。三個語言里Java 的入口類名必須是MainC 的main函數(shù)返回intPython 則直接提交腳本。最容易翻車的不是核心邏輯而是多行讀入時沒有處理好換行。題目說第二行有 N 個整數(shù)但有時候在線平臺的數(shù)據(jù)會包含多余空格或者行尾換行所以 Java 用readLine()后要trim()C 和 Python 用流式讀取反而更省心。還有一個小細節(jié)輸出最后要換行。Java 的println自帶換行C 用\nPython 的print也自帶換行這些都是標(biāo)準(zhǔn)習(xí)慣不會出問題。4.2 我用來驗證的自測數(shù)據(jù)第一次提交前最好先用本地跑幾組數(shù)據(jù)確認答案。我常用的幾組用例放在表格里輸入總需求期望輸出1 / 1101 / 2213 / 3 2 4946 / 1 1 1 1 1 1632 / 60 5011072 / 6 61242 / 1000000000 1000000000200000000031最后一組比較有意思總和是 20 億2^30是 1073741824不夠2^31是 2147483648夠了所以答案是 31。這個用例專門用來檢查 32 位溢出如果你用int累加1000000000 1000000000已經(jīng)溢出成負數(shù)答案就會亂七八糟。4.3 用暴力模擬交叉驗證如果一套思路不太敢信我習(xí)慣寫一個極簡的完全模擬函數(shù)來交叉驗證。給一個 K 次擴容暴力模擬每一天是否夠用然后從 0 開始枚舉 K找到第一個可行的 Kdef ok(a, k): cap 1 k for x in a: if cap x: return False cap - x return True這個函數(shù)模擬的是第一天開始前擴容 K 次到 2^K然后每天都消耗的過程和我們推導(dǎo)的模型完全一致。你可以在本地隨機生成一些數(shù)組用ok暴力找最小 K跟ceil(log2(sum))的代碼對拍多跑幾輪就安心了。實際上由于我們已經(jīng)證明了2^K sum是最小可行條件這個對拍更多是給自己一個心理確認。5. 變體思考如果出題人加限制思路會怎么變5.1 變體一每天最多只能擴容一次如果題目變成每天開始前最多擴一次那就不能把 K 次擴容全部堆到第一天了因為一天只能做一次操作。這個變體不再只取決于總和還要看需求在時間上的分布。比如[1, 1000000]這種輸入總需求大約 1e6K 大概是 20但第 2 天開始之前最多只擴容了 2 次容量只有 4根本扛不住 1000000所以這種版本可能需要重新建模甚至可能無解。出題人如果這么設(shè)計大概率會同時給一個擴容不消耗當(dāng)天空位之類的前提或者允許某天擴容后立即到賬再復(fù)用當(dāng)天容量。遇到這種變體建議先嘗試二分擴容次數(shù)再寫一個貪心模擬去 check比直接莽 DP 要穩(wěn)。5.2 變體二擴容費用每天不同如果每天擴容的單價不同同時又允許一天內(nèi)多次擴容那全部提前到第一天仍然能保證容量覆蓋但不一定省錢第一天的單價可能特別貴把擴容分散到便宜的日子更劃算。但擴容提前又會影響容量覆蓋這里面有一個經(jīng)典的貪心結(jié)構(gòu)總擴容次數(shù) K 其實還是由總和決定問題變成如何在截止時間約束下買 K 次擴容使得費用最小類似帶截止日期的物品選擇。這種題目一般用小根堆做反悔貪心遍歷每一天把當(dāng)天擴容單價加入堆當(dāng)已經(jīng)購買的次數(shù)不滿足前 i 天的覆蓋要求時從堆里取最便宜的歷史價格來補。這個思路可以作為延伸題去練但不是本篇原始題目的標(biāo)準(zhǔn)解法。5.3 面試時怎么表達這個思路最加分如果面試官問的是這道題不要上來就報代碼。建議按這個順序說先把題目抽象成消耗模型強調(diào)容量會消耗而不是只比較峰值接著說我發(fā)現(xiàn)擴容可以提前而且越早擴容基數(shù)越大所以全部提前不劣最后給出2^K 總需求這個充要條件代碼自然就出來了。這個表達方式比直接背模板更能體現(xiàn)你對貪心證明的理解也是這道題真正的考點。我自己在這次復(fù)盤里最大的感觸是筆試題目里那些看起來很規(guī)劃的操作類問題往往可以先問一句這些操作能不能提前能不能重排如果能復(fù)雜度經(jīng)常瞬間從 DP 降到一行公式。以后再遇到任何帶擴容升級購買字樣的題我建議你也先做這一步操作重排的嘗試。