笔试结束那天晚上我在群里看到好几个人发同一道题多多的扩容计划。有人说自己写了100多行的动态规划有人用二分答案套贪心还有人样例过了但心里没底。其实这道题只要看穿一个关键性质代码只有十来行而且三种语言写法几乎一模一样。如果你正在准备大厂春招或者想练一练贪心证明这种笔试思维这篇复盘值得花几分钟看完。我先说结论这道题把所有扩容操作都放到第一天开始前一定是最优的之后的问题就变成初始容量要多大才能吃下总消耗答案是总需求和的ceil(log2)。下面我把整个推导过程、三份参考代码、在线测试时的输入输出细节和常见坑位都拆开讲。1. 题目模型先把题面抽象成水池模型1.1 考场上拿到的题面我按记忆把原题复述成一个标准 OJ 形式方便后面讨论。多多有一台初始容量为 1 的服务器接下来 N 天第 i 天业务会产生 a_i 的负载服务器当天必须把负载全部处理完。处理完的负载会消耗掉对应容量容量不会自动恢复。每天业务开始前多多可以花 1 金币做一次扩容每次扩容让当前容量翻倍。扩容可以执行任意次容量是永久提升的问最少花多少金币才能保证所有天都不爆容量。输入格式是两行第一行一个整数 N第二行 N 个整数 a_1 到 a_N。输出一行一个整数表示最少金币数。约束方面N 最大可以到 10 万a_i 最大可以到 10 的 9 次方所以总和会超过 32 位整数范围这一点后面会专门说。给一个标准样例输入5 3 2 4 5 1输出是4。这 5 天的总需求是 151 扩容 4 次后变成 16初始容量 16 已经大于总需求 15所以 4 次就够。模拟一下第 1 天消耗 3 剩 13第 2 天消耗 2 剩 11第 3 天消耗 4 剩 7第 4 天消耗 5 剩 2第 5 天消耗 1 剩 1全程不会爆容量。1.2 这题的关键是消耗而不是峰值很多人会第一眼把它看成容量峰值题只要服务器容量一直大于等于所有 a_i 的最大值不就行了这个想法只适用于容量不会因为处理任务而减少的版本。如果容量会被消耗情况就完全不同。举个例子输入[6, 6]。只看单日峰值 6初始扩容 3 次到 8 似乎就够了因为ceil(log2(6)) 3。但第一天消耗 6 之后剩余容量只有 2第二天还要消耗 6明显不够。实际需要初始扩到 16也就是 4 次扩容。所以峰值视角会让你漏掉前一天消耗之后后一天可能不够用这种关键时间点。理解到这里后面推导就顺了。1.3 按天模拟为什么能过样例却可能不是最优我猜不少人考场上的第一反应是写一个按天模拟的贪心当前容量不够当天的 a_i就不断扩容直到够用然后current - a_i把扩容次数累加。这个方案能跑出一个可行结果甚至能过不少样例但它不是全局最优。拿[5, 20]来试。按天模拟第 1 天开始时容量是 1要处理 5需要扩到 8做了 3 次扩容剩 3。第 2 天要处理 20当前 3 不够从 3 翻倍到 6、12、24又做 3 次扩容一共 6 次。但全局最优只要 5 次第一天开始前直接把容量扩到 32做 5 次扩容第一天消耗 5 剩 27第二天消耗 20 剩 7全程足够。为什么按天模拟会输因为它总是在不够了才扩这时候容量基数是小了的如果提前扩容翻倍的基数更大同样的扩容次数能带来更多容量。接下来我用一个严格的交换论证把这个直觉变成结论。2. 核心结论扩容全部提前一定不亏2.1 一个交换论证所有扩容都可以挪到第一天设任意一个可行的扩容方案总共有 K 次扩容。我们可以证明一定存在另一个仍然可行、而且不会花更多金币的方案它让这 K 次扩容全部发生在第一天开始前。理由是这样的无论扩容发生在哪一天每次扩容都是把当时的容量翻倍。如果某次扩容发生在第 j 天那么在那一天开始前服务器已经消耗掉前 j-1 天的负载容量是某个值 C。如果把这同一次扩容挪到第一天开始前当时还没有任何消耗容量不小于 C翻倍之后得到的容量也一定不小于原来那次扩容之后得到的容量。把一次扩容提前只会让之后每一天的可用容量变多不会让任何一天变差。反复应用这个调整所有扩容都能一步步挪到第一天而每天开始前的容量只会变大。最终我们得到一个容量曲线第一分钟就把容量从 1 翻倍 K 次到 2^K之后再不扩容每天只消耗不增加。更简洁地说一个总共 K 次扩容的方案在任何时刻的容量都不可能超过全部扩容提前到第一天的 2^K 减去已经消耗的总量。因为后者相当于把 K 次翻倍全部作用在了最大基数的初始容量上。所以最优方案一定可以写成第一天扩满 K 次之后纯消耗这种简单形式。2.2 充要条件初始容量覆盖总需求即可一旦确定所有扩容都放在第一天问题就变成了一个非常干净的条件。设总共扩容 K 次初始容量就是 2^K。用 S_i 表示前 i 天的负载总和也就是前缀和。第 i 天开始前服务器剩余容量是 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 都是正整数前缀和 S_i 是单调不减的所以最大的 S_i 就是最后一天结束后的总消耗SUM a_1 ... a_N。于是条件变成只要2^K SUM就行其他中间天自然都能满足。反过来如果2^K SUM那么所有负载的总容量都接不住最后一天之前一定存在某个时刻爆容量。因此充要条件就是初始容量不小于总需求答案就是最小的 K 满足2^K SUM也就是ceil(log2(SUM))。这个结论也解释了一个容易踩的误区不要去管某一天的需求波动有多大也不用做任何剩余容量会不会不够的判断只需要把所有数字加起来然后看 2 的多少次方能盖住这个总和。2.3 几个直觉测试为什么看总需求是对的我给自己编了几个例子用来快速验证结论是不是真的合理。第一个例子是[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 才稳妥。这个例子特别适合拿去反驳只看最大值的思路。2.4 写代码前的两个精度提醒计算ceil(log2(SUM))时不要直接用Math.log或者log函数取对数再向上取整。当 SUM 很大的时候浮点数计算会出现精度误差尤其是 SUM 刚好落在 2 的幂次边界附近误差可能导致答案差 1。笔试环境里最稳妥的做法是循环倍增用一个cap 1的变量不断左移直到cap SUM左移次数就是答案。这样既没有浮点误差代码也直观。另一个提醒是数据类型。N 最大 10 万a_i 最大 1e9总和最大可以到 1e14。Java 里要用longC 里要用long longPython 无所谓但要注意读入方式。如果你在 Java 里用了int总和直接溢出答案会变成负数或者完全错误这是笔试里最容易出现也最难受的失误。3. Java / C / Python 三份参考实现3.1 Java 实现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 这边有个细节不要用Scanner。N 到 10 万时 Scanner 还能撑住但nextLong()在数据量大的时候会比较慢而且BufferedReader的写法也不复杂笔试时直接用更稳妥。注意读第二行时用StringTokenizer分割避免字符串数组占用多余空间。3.2 C 实现#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 实现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()快很多尤其是数据量大的时候。int(data[i])直接转换Python 的整数没有位数上限所以不用担心总和溢出。如果担心read()占内存也可以改用sys.stdin.readline()逐行读但笔试场景下read()更方便。3.4 三份代码的对比与时间复杂度语言核心注意点时间复杂度空间复杂度JavaBufferedReader longO(N)O(1) 额外空间Clong long ios 加速O(N)O(1) 额外空间Pythonsys.stdin.buffer.readO(N)O(N) 读入数据或逐行读 O(1)三种写法本质上是同一套逻辑先累加总和再循环算 2 的幂次数。时间复杂度都是 O(N)空间上除了输入缓冲之外都是常数级。N 到 10 万时这个复杂度非常宽裕跑起来没有任何压力。这道题真正的分水岭不是算法复杂度而是能不能想到全部提前扩容这一步。4. 在线测试平台怎么提交怎么自测4.1 OJ 提交时的输入输出细节在线测试平台通常要求从标准输入读数据把结果打印到标准输出。三个语言里Java 的入口类名必须是MainC 的main函数返回intPython 则直接提交脚本。最容易翻车的不是核心逻辑而是多行读入时没有处理好换行。题目说第二行有 N 个整数但有时候在线平台的数据会包含多余空格或者行尾换行所以 Java 用readLine()后要trim()C 和 Python 用流式读取反而更省心。还有一个小细节输出最后要换行。Java 的println自带换行C 用\nPython 的print也自带换行这些都是标准习惯不会出问题。4.2 我用来验证的自测数据第一次提交前最好先用本地跑几组数据确认答案。我常用的几组用例放在表格里输入总需求期望输出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已经溢出成负数答案就会乱七八糟。4.3 用暴力模拟交叉验证如果一套思路不太敢信我习惯写一个极简的完全模拟函数来交叉验证。给一个 K 次扩容暴力模拟每一天是否够用然后从 0 开始枚举 K找到第一个可行的 Kdef ok(a, k): cap 1 k for x in a: if cap x: return False cap - x return True这个函数模拟的是第一天开始前扩容 K 次到 2^K然后每天都消耗的过程和我们推导的模型完全一致。你可以在本地随机生成一些数组用ok暴力找最小 K跟ceil(log2(sum))的代码对拍多跑几轮就安心了。实际上由于我们已经证明了2^K sum是最小可行条件这个对拍更多是给自己一个心理确认。5. 变体思考如果出题人加限制思路会怎么变5.1 变体一每天最多只能扩容一次如果题目变成每天开始前最多扩一次那就不能把 K 次扩容全部堆到第一天了因为一天只能做一次操作。这个变体不再只取决于总和还要看需求在时间上的分布。比如[1, 1000000]这种输入总需求大约 1e6K 大概是 20但第 2 天开始之前最多只扩容了 2 次容量只有 4根本扛不住 1000000所以这种版本可能需要重新建模甚至可能无解。出题人如果这么设计大概率会同时给一个扩容不消耗当天空位之类的前提或者允许某天扩容后立即到账再复用当天容量。遇到这种变体建议先尝试二分扩容次数再写一个贪心模拟去 check比直接莽 DP 要稳。5.2 变体二扩容费用每天不同如果每天扩容的单价不同同时又允许一天内多次扩容那全部提前到第一天仍然能保证容量覆盖但不一定省钱第一天的单价可能特别贵把扩容分散到便宜的日子更划算。但扩容提前又会影响容量覆盖这里面有一个经典的贪心结构总扩容次数 K 其实还是由总和决定问题变成如何在截止时间约束下买 K 次扩容使得费用最小类似带截止日期的物品选择。这种题目一般用小根堆做反悔贪心遍历每一天把当天扩容单价加入堆当已经购买的次数不满足前 i 天的覆盖要求时从堆里取最便宜的历史价格来补。这个思路可以作为延伸题去练但不是本篇原始题目的标准解法。5.3 面试时怎么表达这个思路最加分如果面试官问的是这道题不要上来就报代码。建议按这个顺序说先把题目抽象成消耗模型强调容量会消耗而不是只比较峰值接着说我发现扩容可以提前而且越早扩容基数越大所以全部提前不劣最后给出2^K 总需求这个充要条件代码自然就出来了。这个表达方式比直接背模板更能体现你对贪心证明的理解也是这道题真正的考点。我自己在这次复盘里最大的感触是笔试题目里那些看起来很规划的操作类问题往往可以先问一句这些操作能不能提前能不能重排如果能复杂度经常瞬间从 DP 降到一行公式。以后再遇到任何带扩容升级购买字样的题我建议你也先做这一步操作重排的尝试。