先给结论拼多多2026春招笔试第二题“多多的充电计划”本质上是一道披着共享电动车外衣的调度题考察的就是贪心 优先队列 截止时间这三个点。你把题面里的“充电桩”换成“CPU”、“电动车”换成“进程”它就是操作系统里最经典的带截止期限的单机任务调度。这篇文章我会从题目拆解、贪心证明、Java/C/Python三种实现、在线自测数据到常见坑位一次讲透不管是正在准备春招的应届生还是想系统刷贪心专题的选手都可以直接照着写代码复制到本地就能跑通。1. 题目原文与题意拆解1.1 从生活场景到算法题面这道题的实际背景并不复杂多多在园区投放了一批共享电动车骑手们晚上陆续把车骑回充电站充电站只有一个充电桩同一时刻只能给一辆车充电而且充电一旦开始就不能中断。每辆车因为第二天早上的出车安排不同都有一个“最晚完成充电”的硬性时间。问是否存在一种充电顺序能让所有车都在各自的规定时间前充满。网上流传的版本在输入输出细节上可能有些出入但核心模型非常稳定我把它整理成下面这个标准题面方便我们讨论算法有 n 辆电动车第 i 辆车充满电需要 c[i] 小时并且必须在 d[i] 时刻之前完成充电。充电站从 0 时刻开始运营只有一个充电桩同一时刻只能给一辆车充电充电过程中不可中断。请判断是否存在一种充电顺序使得所有电动车都能在各自的规定时间前充满。如果可行输出 YES 和所有车都完成充电的最早时刻如果不可行输出 NO 和最多能给多少辆车充满。为什么“最早完成时刻”和“最多充电数量”是可以一起求的因为这两件事本质上是同一个贪心过程的两个输出角度。这个我们放到第二节的算法里看就清楚了。现在先把输入输出格式定下来这样后面的代码才能有统一的参照。1.2 输入输出约定与样例解读输入格式第一行一个整数 n表示电动车数量1 ≤ n ≤ 10^5。第二行 n 个整数c[1], c[2], ..., c[n]表示每辆车的充电时长小时。第三行 n 个整数d[1], d[2], ..., d[n]表示每辆车最晚完成充电的时间小时。数据范围上0 ≤ c[i] ≤ 10^90 ≤ d[i] ≤ 10^9。注意答案可能超过 32 位整数范围这个问题后面会反复强调Java 用 longC 用 long longPython 无所谓。输出格式第一行输出 YES 或 NO。若第一行为 YES第二行输出一个整数表示所有车都完成充电的最早时刻。若第一行为 NO第二行输出一个整数表示最多能给多少辆车充满电。我构造两个样例一个可行一个不可行先把流程走一遍。样例一不可行3 3 2 4 6 5 7输出NO 2解释一下按截止时间排序后车辆变为充电时长 2截止 5、充电时长 3截止 6、充电时长 4截止 7。前两辆依次安排充电结束时刻分别是 2 和 5都没有超时。第三辆如果也要充结束时刻会变成 5 4 9超过了 7所以最多只能完成前两辆。输出 NO 和 2。样例二可行4 4 1 1 2 4 5 6 8输出YES 8这个例子对应的充电顺序是0 到 4 充第一辆4 到 5 充第二辆5 到 6 充第三辆6 到 8 充第四辆。每辆车的完成时刻恰好卡在截止时间之内所有车都能充满最早完成时刻就是总时长 8。到这里题已经读透了下面进入最核心的部分这个贪心策略到底怎么想出来又为什么是对的。2. 贪心策略与正确性证明2.1 直觉得出的第一步按截止时间排序先想一个最简单的情况如果所有车的截止时间都相同应该按什么顺序充电显然先充耗时短的也就是短作业优先。因为充电是可以连续占用充电桩的只有一个桩所有车的总耗时固定短作业优先可以让“已完成的车数”随时间增长得最快而且在截止时间相同的前提下任何顺序能完成的车数上限都是一样的短作业优先只是一个不会更差的方案。但题目里每辆车的截止时间不同情况就变了。如果还单纯按耗时排序很容易出现一个问题一个只需要 1 小时的车因为耗时短被排在前面充但它截止时间很晚而另一辆耗时 2 小时、截止时间很近的车被排到了后面结果来不及。举个反例两辆车A 耗时 1 截止 100B 耗时 2 截止 2。按耗时排序会先充 A充完已经 1 点再充 B 结束是 3 点B 超时。但先充 B2 点完成再充 A3 点完成全部来得及。所以第一步就是要按截止时间从小到大处理把“最急迫”的任务先纳入考虑。这个思路在调度问题里几乎是铁律截止时间越早越应该优先被安排。后面的贪心过程也都是在“按截止时间排序”这个前提下展开的。2.2 大根堆维护已选集合弹出谁、为什么按截止时间排序后我们用 cur 表示当前已经安排掉的充电总时长。因为只有一个充电桩cur 同时也代表当前时刻。接下来对每辆车按顺序处理采用“先假设要它不行再放弃一辆”的策略先把当前车辆的充电时长 c[i] 加入一个“已选择”的大根堆同时 cur c[i]。如果此时 cur 超过了当前车辆的截止时间 d[i]说明在已经选择的这些车里必须至少放弃一辆才能把总耗时压回到 d[i] 以内。关键问题是放弃哪一辆“已选择”的车里有一辆耗时很长的可能占了很大一块时间放弃它能立刻让 cur 下降一大截也有一辆耗时很短的放弃它对 cur 几乎没影响。为了给后续车辆留出更多空间显然应该放弃耗时最长的那辆。这就是大根堆的用途每次需要放弃时直接弹出堆顶也就是当前已选集合里充电时长最大的那辆车。为什么“已经选择的这些车”一定可以通过调整顺序都按时完成这里有个很重要的性质我们按截止时间升序扫描堆里所有车的截止时间都不晚于当前这辆车的 d[i]。只要这些车的总耗时不超过 d[i]就一定存在一个合法顺序把它们都安排好——因为截止时间最紧的车可以最先充剩下的车按截止时间顺序依次往后排最晚完成时刻就是总耗时而总耗时不超过 d[i]也就不会超过任何一辆已选车的截止时间。2.3 正确性证明的几个关键点很多同学能理解这个贪心的“直觉”但要真说服自己它是最优的还需要一点证明。这里我给出一个比较好接受的不变式证明思路。维护一个不变式扫描到第 i 辆车时堆中的集合是“前 i 辆车里在保证能全部按时完成的前提下数量最多、且总时长最小的可行集合”。注意是两个条件同时满足数量优先数量相同再比总时长。每来一辆新车我们先把它放进去数量加一。如果总时长没有超过当前截止时间那么这个集合就保持了“数量最多”的性质。如果总时长超过了说明在当前这个数量下无法全部完成必须从集合里扔掉一辆。扔掉哪一辆能保证扔掉后总时长最小显然是耗时最大的那一辆。于是数量回退到上一轮的值但集合的总时长比上一轮更小这就同时维持了“数量最多”和“总时长最小”。这个不变式的价值在于它不只是证明了“最多能完成多少辆”是正确答案还证明了我们找到的这个集合本身就是一个可行的调度方案。完成所有车之后如果堆大小等于 n说明没有任何一辆被放弃cur 就是所有车的总耗时也是最早完成时刻如果堆大小小于 n说明过程中至少放弃了一辆此时输出 NO 和堆大小。还需要强调一个容易被忽略但特别有用的性质一旦发生过弹出操作最终答案一定是 NO。因为每次弹出都意味着放弃了一辆已经扫描过的车堆的大小永远不会再回到 n。所以代码里最后判断堆大小是否等于 n既简洁又准确。2.4 复杂度和边界条件整个算法由三部分构成一次排序 O(n log n)一次单层循环 O(n)每次入堆和出堆都是 O(log n)。总复杂度 O(n log n)空间复杂度 O(n)。这个复杂度在 n 10^5 的笔试数据量下非常安全三份代码在 1 到 2 秒的时限内都能跑完。边界条件还有几个值得提前想清楚c[i] 0 的车耗时为零加进堆里不影响 cur但堆的大小会计入完成数量。这其实是合理的0 小时的充电任务当然可以“瞬间完成”。d[i] 0 且 c[i] 0这种情况在判断 cur d[i] 时会立刻触发弹出最终该车不会被算入完成数量符合直觉。n 1 时如果 c[1] ≤ d[1]输出 YES 和 c[1]否则输出 NO 和 0。这个边界用来做自测非常方便。贪心部分到这里已经完整了。下面进入实战环节把同样的逻辑分别用 Java、C、Python 写出来。3. 三种语言实现对照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()); long[] c new long[n]; long[] d new long[n]; StringTokenizer st new StringTokenizer(br.readLine()); for (int i 0; i n; i) c[i] Long.parseLong(st.nextToken()); st new StringTokenizer(br.readLine()); for (int i 0; i n; i) d[i] Long.parseLong(st.nextToken()); Integer[] idx new Integer[n]; for (int i 0; i n; i) idx[i] i; Arrays.sort(idx, (a, b) - Long.compare(d[a], d[b])); PriorityQueueLong pq new PriorityQueue(Comparator.reverseOrder()); long cur 0; for (int i 0; i n; i) { int id idx[i]; cur c[id]; pq.offer(c[id]); if (cur d[id]) { cur - pq.poll(); } } if (pq.size() n) { System.out.println(YES); System.out.println(cur); } else { System.out.println(NO); System.out.println(pq.size()); } } }Java 这里有三个坑要重点提醒。第一PriorityQueue 默认是小根堆你要的是大根堆所以必须传入Comparator.reverseOrder()。忘了这一步弹出的是耗时最小的车整个贪心全部颠倒结果必然错误。第二数据范围必须用 long。c 和 d 都是 10^9 级别n 是 10^5cur 累加最大能到 10^14int 完全扛不住。Java 里 PriorityQueue 的泛型因此也得写成PriorityQueueLong不然放不进去。第三排序时不要直接排序 c 数组或 d 数组因为两个数组的对应关系会丢。我这里的做法是创建一个索引数组 idx按 d[idx] 排序然后通过 idx 同时访问 c 和 d干净且不容易出错。输入方面n 只有 10^5用 Scanner 其实也能过但笔试环境不稳定我习惯直接用 BufferedReader StringTokenizer几行代码而已换来更稳的读取速度。3.2 C 实现与要点#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll c(n), d(n); for (int i 0; i n; i) cin c[i]; for (int i 0; i n; i) cin d[i]; vectorint idx(n); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [](int a, int b) { return d[a] d[b]; }); priority_queuell pq; ll cur 0; for (int i 0; i n; i) { int id idx[i]; cur c[id]; pq.push(c[id]); if (cur d[id]) { cur - pq.top(); pq.pop(); } } if (pq.size() (size_t)n) { cout YES\n cur \n; } else { cout NO\n pq.size() \n; } return 0; }C 版本是最省心的原因很直接priority_queue 默认就是大根堆push、top、pop 一套下来完全符合贪心需求不需要任何额外转换。有两个小地方要注意。一是ios::sync_with_stdio(false)和cin.tie(nullptr)最好加上否则在数据量大的时候 cin 会比 scanf 慢不少。二是pq.size()返回的是 size_t和 n 比较时建议显式转一下类型避免编译器报警告输出的时候直接输出 pq.size() 也没问题它会自动转成整数。关于#include bits/stdc.h笔试平台基本都能用但在本地 VSCode 里如果没有配置好 GCC 的 include 路径可能会报找不到头文件。我的建议是日常练习可以写成具体的头文件比如iostream、vector、queue、algorithm、numeric笔试时再用万能头省时间。3.3 Python 实现与要点import sys import heapq def main(): data list(map(int, sys.stdin.buffer.read().split())) n data[0] c data[1:1 n] d data[1 n:1 2 * n] order sorted(range(n), keylambda i: d[i]) heap [] cur 0 for i in order: cur c[i] heapq.heappush(heap, -c[i]) if cur d[i]: cur heapq.heappop(heap) if len(heap) n: print(YES) print(cur) else: print(NO) print(len(heap)) if __name__ __main__: main()Python 的 heapq 默认是小根堆要模拟大根堆标准做法是存负值把 -c[i] 放进堆里堆顶就是负得最多的也就是原值最大的。这里有一个非常容易写错的地方弹出堆顶时堆顶是负值所以cur heapq.heappop(heap)实际上是在“加上一个负数”效果等于减去对应的充电时长。很多同学会下意识写成cur - heapq.heappop(heap)那就是加上了时长整个结果直接崩掉。我在代码里用cur heapq.heappop(heap)的写法就是为了让负负得正这个操作读起来更顺。输入方面Python 用input()读 10^5 行级别的数据会比较慢这道题虽然是两行大数组但我也推荐直接用sys.stdin.buffer.read()一次性读进来再切分速度会快很多。这段代码在 n 10^5 的数据量下实测是稳的不需要额外用 PyPy 也能在时限内跑完。3.4 三份代码的差异对比语言堆的默认类型大根堆实现方式最容易踩的坑Java小根堆new PriorityQueue(Comparator.reverseOrder())忘了传比较器泛型误用 IntegerC大根堆直接用priority_queuellpq.size()与 int 比较类型不一致Python小根堆入堆存-c[i]弹出后误写成cur - heappop三份代码的核心逻辑完全一致差异只在语言特性上。看懂了任意一份其他两份只是换皮。下面说一个更实际的问题代码写出来之后怎么确认它是对的以及哪些错误是高频的。4. 在线自测与高频错误排查4.1 直接可用的自测数据写完代码第一件事不是直接交而是用小数据自己验一遍。下面这四组数据够用了前两组覆盖 YES 和 NO 分支后两组覆盖边界。第一组全可行4 4 1 1 2 4 5 6 8预期输出YES 8第二组不可行3 3 2 4 6 5 7预期输出NO 2第三组单辆车能充1 5 5预期输出YES 5第四组单辆车来不及1 6 5预期输出NO 0第五组全零边界2 0 0 0 0预期输出YES 0第六组大数验证 64 位2 1000000000 1000000000 1000000000 2000000000预期输出YES 2000000000第六组特别重要它能直接暴露你用 int 带来的溢出问题。如果你 Java 版用 int 写 cur输出会变成一个负数这种错误在笔试样例里通常不会出现但裁判数据一上就翻车。4.2 五个最容易翻车的细节这些年刷题见了太多在这道题上翻车的情况我总结了五个高频错误按出现频率排序。第一个堆类型搞反。Java 默认小根堆、Python 默认小根堆只有 C 默认是大根堆。这个错误在样例少的时候根本看不出来因为“少做一辆车”和“多做一辆车”的差别在简单数据里可能不体现但一旦出现多辆耗时差异大的车结果立刻错乱。我的建议是写代码前先在注释里写一句“这里需要大根堆”再动手。第二个排序时破坏了对应关系。比如单独把 d 排序然后 c 还是原顺序或者用Arrays.sort(c)把 c 也排了这样 c 和 d 的对应关系全毁了。正确做法永远是用索引数组排序或者用 pair 打包。第三个判断条件写错。有人会写成“先判断 cur c[i] d[i]如果超了就跳过这辆车”这个做法在局部是合理的但全局上不够优。因为超时的时候可能更应该放弃的是之前某辆耗时很长的车而不是当前这辆。正确顺序一定是“先入堆再判断”让堆帮你决定放弃谁。第四个cur 的类型不够。前面反复强调过10^9 乘以 10^5 是 10^14int 必然溢出。C 写 int、Java 写 int都会在极限数据上爆炸。这个错误一旦发生你甚至很难定位因为小数据全都正确。第五个Python 输入太慢。如果笔试平台对 Python 时限给得很紧用 input() 读大数组会有风险。统一用sys.stdin.buffer.read()分片读取这个习惯值得养成。4.3 去哪些平台提交验证这道题和 LeetCode 630 Course Schedule III 是同一类模型你可以在 LeetCode 上搜“630”直接练习核心逻辑不同点只是 LeetCode 要求返回最多能完成的数量而本题还要判断是否全部完成并输出最早完成时间。拼多多的原题一般出现在校招笔试平台比如牛客网或者赛码网的真题题库里。你搜索“拼多多 充电计划”或者“拼多多 春招 真题”就能找到对应题目在线评测的输入输出格式以平台页面为准代码本体不需要改动。还有一个验证手段本地自测时构造一个“故意需要弹出”的数据用三种语言分别跑确认输出一致。比如手动模拟一个场景第一辆耗时很大但截止晚第二辆截止很紧第三辆截止中等。如果三份代码输出相同基本可以确定算法理解没问题。5. 变体训练与考场心得5.1 可抢占充电更简单的判定模型如果题目改成充电可以中断也就是一辆车充到一半可以先让给别人充之后再回来接着充那么问题会变得更简单反而不需要优先队列了。可抢占的情况下最优策略是“最早截止时间优先”也就是 EDF 策略。判定条件很漂亮按截止时间排序后只要对每一个前缀都有“前 i 辆车总充电时长 ≤ d[i]”就一定存在可行调度。这个条件比不可抢占版本更强也更直观。从算法角度理解这个变化很有意思可抢占相当于你把每个充电任务切碎成无限小的片段充电桩可以任意切换那么调度的自由度大大提高可行性判断从“贪心堆”退化成了“排序前缀和”。笔试中如果看到“充电可以中断”这种描述优先想前缀和别急着写堆。5.2 多充电桩与更多变体如果充电桩从 1 个变成 m 个问题就变成了多机调度。m 比较小的时候可以用一个长度为 m 的最小堆维护每个充电桩的空闲时间按截止时间排序后依次分配m 很大的时候可能要结合二分答案来判定可行性。再往远一点说如果每辆车还有一个“最早可以开始充电的时间”那就变成了带到达时间和截止时间的单机调度模型更接近真实的操作系统任务调度。这类题的解题框架仍然逃不出排序 堆只是排序的键和堆维护的信息会多一些。还有一类常见变体是求“最少需要几个充电桩才能让所有车都按时充满”那就变成了区间重叠问题用差分数组或者扫描线做和今天这道题的思路又不一样了。我建议你把这些变体归类整理刷题的时候放在一起对比效果远好于一个一个孤立地刷。5.3 考场上的识别与策略最后聊点应试经验。笔试是一个限时场景识别题目类型比会写代码更值钱。看到“只有一个充电桩”“同一时刻只能”“最多能完成”“是否可行”这些关键词组合第一反应就应该是贪心 优先队列。我的实操习惯是读题之后先不急着写代码在草稿纸上写三行字——排序键是什么、堆里维护什么、什么条件下弹出。把这三行写清楚再动手代码几乎是一遍过。反过来如果上来就模拟“每辆车来了怎么排队”十有八九会陷入复杂的条件分支里把自己绕晕。还有一个建议这道题的代码量很小三种语言都能在三十行左右写完。但正因为代码短反而更容易忽略数据范围这种“看不见”的问题。交卷前留 30 秒检查一遍所有变量类型值得。我个人刷这类调度题最大的收获是把“先假设、超时后放弃最重的”这个贪心范式吃透了。它不止能解充电计划很多资源分配类的题目都可以套用。你下次再碰到类似的题不妨也试试用这三步去想排序、入堆、超时弹出。这套思路一旦形成碰到新题就不会慌。