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