拼多多2026年春招3月15日这场笔试第二题“多多的充电计划”考得很典型Java、C、Python三种语言我都写了完整实现也把踩坑点捋了一遍。乍一看这道题像模拟题好像按顺序开车、电量不够就充电就行真动手才发现它考的是贪心加优先队列的经典模型和LeetCode 871那道“最低加油次数”是同一个套路。准备冲大厂笔试的同学这种“消耗型路径 补充点 最小补充次数”的题值得吃透因为它几乎每年都会换层皮出现在各家笔试里。这篇文章我不会只贴代码。我会先把题目还原清楚然后把“为什么用贪心”“为什么需要大顶堆”讲明白再给三种语言的完整实现和自测用例最后聊聊这类题的常见变形。你照着这个思路捋一遍下次再碰到“充电”“加油”“补给”类型的题应该能直接形成条件反射。1. 题面还原与这道题的考点定位1.1 完整题面基于常见版本整理因为不同渠道流传的版本在数据范围和细节上会有一点差异我先按经典模型把题面整理如下下文所有思路和代码都基于这个版本多多开一辆电动小车从数轴上的0位置出发要送包裹到target位置。小车每行驶1单位距离消耗1单位电量出发时电量正好等于电池容量capacity。途中有n个充电站第i个充电站位于positions[i]每个充电站最多只能使用一次一旦选择在该站充电可以立即补充charge[i]单位的电量。注意补充的电量没有“上限截断”的问题也就是说电量可以是累加的不需要考虑“充到一定程度就充不进去”的物理限制。要求计算出到达target所需的最少充电次数如果无论如何都无法到达输出-1。输入格式通常是第一行target capacity n 接下来n行position charge例如10 6 4 2 3 4 4 5 5 8 2对应输出1。这个样例很经典建议自己先动手算一算再往下看思路。1.2 为什么这不是一道“见站就充”的模拟题很多人第一反应是每到一个站看电量不够就充够就继续走。这个思路在部分数据下能过但它不是最优的。举个反例。target10, capacity5充电站依次是(2,2), (3,1), (4,5), (7,3)。如果“见站就充”你可能会在2号位置充2在3号位置充1在4号位置充5最后充电次数明显偏多。实际上最优方案是2号、3号都不充硬撑到4号位置此时电量虽然只剩1但回顾之前经过的所有站点4号本身能充5一次充电就能撑到终点总充电次数只有1次。这个例子说明关键点到底在哪个站充电不应该在当前时刻立刻决定而应该先“欠着”。等到电量真的撑不到下一站时再回过头从已经经过的所有充电站里挑一个最划算的来补电。这种思路在算法竞赛里有个形象的说法优先队列存“后悔药”。1.3 考点地图贪心、大顶堆与排序的组合拳这道题的考点非常清晰排序站点给出的顺序不保证按位置递增必须自己排序。贪心每次电量不足时从已过站点中选充电量最大的那个补电。大顶堆维护“已经路过但还没充电的站点”的可充电量保证能快速拿到最大值。边界处理无解判定、终点不能充电、电量刚好为0时可以继续走。这四件事组合起来就是面试官很喜欢考的“贪心 优先队列”模型。代码量不大三四十行但模型识别错了写起来就会很痛苦。2. 核心思路把“充不充电”改成“什么时候反悔”2.1 关键观察先欠着撑不住再补具体的做法是这样把target也当作一个站点加入列表但它的充电量是0且不能真的充电只是为了让循环统一处理“开到终点”这一步。按位置从小到大遍历所有站点。每到一个站点先让电量减去当前坐标与上一个坐标的差值模拟行驶消耗。如果行驶后电量变成负数说明不补电就到不了当前站点。此时从大顶堆里取出最大的充电量充电次数加1电量加上这个值继续检查电量是否还小于0如果还是小于0就继续取堆里的值充电。如果堆已经取空了电量还是负的说明所有能用的充电站都用了还是到不了这里直接返回-1。顺利到达当前站点后把该站点提供的充电量放入大顶堆作为以后“反悔”的选项。终点不入堆。这个流程里的关键动作是“先欠着”。每次路过充电站时不急着充电而是把它的充电量扔进堆里。等真正缺电的时候再从所有路过但没充电的站点里选一个补上。2.2 贪心正确性为什么选最大充电量一定不会错有人会问为什么缺电的时候取堆里最大的充电量就一定能得到最小充电次数这里需要把贪心正确性讲透。先看“在哪个站充”的问题。假设现在我们缺电了必须从经过的站点里选一个来充。如果最优解选了一个充电量较小的站点A而没有选充电量更大的站点B那么我们把这次充电换成在B站充充电次数不变但补到的电量变多了后续的电量只会更多不会更差。通过这种交换总能得到一个“每次缺电时都选最大充电量”的最优解。所以取堆顶最大值是安全的。再看“什么时候充”的问题。有人可能觉得早充电不是更好吗其实不会。考虑一次在较早站点发生的充电它补充的电量在后续行驶中会被消耗效果等于在一个更晚的站点补充等量或更少的电但充电次数一样是1次。而如果早充电的电量足够支撑到终点那么晚一点充也一定足够。换句话说提前充电既不会减少充电次数还可能因为电量兜底而白白浪费一次充电机会。所以“撑不住再充”这个策略是最优的保险做法。2.3 复杂度分析与数据范围预判整体复杂度是O(n log n)对站点排序需要O(n log n)每个站点最多入堆一次、出堆一次堆操作每次O(log n)所以也是O(n log n)空间复杂度O(n)。笔试里n通常给到10^5这个复杂度完全能跑。要特别注意target和capacity在10^9量级Java里用longC里用long long只有Python不用操心溢出问题。3. 逐步推演从样例到边界条件3.1 样例手算看看大顶堆到底怎么变化拿最开始那个样例走一遍完整流程。排序后的站点是(2,3), (4,4), (5,5), (8,2), (10,0)起点0满电6。当前站点行驶消耗后电量是否需要充电堆内容大顶堆充电动作充电次数0起点6否空无024否[3]无042否[4,3]无051否[5,4,3]无08-2是[5,4,3]取出5电量变成31101否[4,3]再加入8的2无1注意走到8的时候减去距离3之后电量变成负数从堆里取出最大值5电量变成3已经能覆盖剩余路段了。8自身还能充2但在本例中不需要用。最终到终点时电量还剩1总充电次数是1。这个推演也解释了为什么站点8的充电量不能提前用它本身就是一个“可以欠着”的资源等到真正缺电时再取。3.2 边界条件与无解判定有几个边界情况是必须考虑的从起点就撑不到第一个站点比如target2, capacity1, n0初始电量1连第一个点都到不了堆是空的直接返回-1。满电直接能到终点比如target10, capacity10, n0全程不用充电返回0。电量刚好变成0这种情况不算负数不需要充电还能继续行驶到下一个站点。比如当前位置电量1下一站距离1行驶后电量0OK。站点位置乱序输入必须排序否则“先欠着”这套逻辑直接失效。终点不能充电把终点加入列表是为了统一处理但要单独判断不能把终点的充电量放进堆里。充电量是0的站点入堆也没问题反正取出来也补不了多少但会增加无用的堆操作代码里可以加一个if (charge 0)的判断优化一下。4. 三个版本的完整代码与工程细节4.1 Java版PriorityQueue的反序与long溢出问题Java的PriorityQueue默认是小顶堆要改成大顶堆需要传一个比较器。我用Collections.reverseOrder()比较省事。另一个容易踩的坑是站点坐标、电量、距离这些值都可能到10^9累加以后容易超int所以统一用long。import java.io.*; import java.util.*; public class Main { static class Station { long pos, charge; Station(long p, long c) { pos p; charge c; } } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); long target Long.parseLong(st.nextToken()); long capacity Long.parseLong(st.nextToken()); int n Integer.parseInt(st.nextToken()); ListStation list new ArrayList(); for (int i 0; i n; i) { st new StringTokenizer(br.readLine()); long pos Long.parseLong(st.nextToken()); long charge Long.parseLong(st.nextToken()); list.add(new Station(pos, charge)); } list.add(new Station(target, 0)); list.sort(Comparator.comparingLong(a - a.pos)); PriorityQueueLong maxHeap new PriorityQueue(Collections.reverseOrder()); long battery capacity; long cur 0; int cnt 0; for (Station s : list) { battery - s.pos - cur; while (battery 0 !maxHeap.isEmpty()) { battery maxHeap.poll(); cnt; } if (battery 0) { System.out.println(-1); return; } if (s.pos ! target) { maxHeap.offer(s.charge); } cur s.pos; } System.out.println(cnt); } }这里想特别提醒一点比较器尽量不要写成(a, b) - (int)(b - a)虽然很多教程这么写但一旦数值超过int范围相减会溢出比较结果直接错乱。用Collections.reverseOrder()或者Long.compare(b, a)都更稳。4.2 C版priority_queue默认大顶堆的天然优势C的priority_queue默认就是大顶堆这道题里简直是为它量身定做的少写一个比较器。vectorpairlong long,long long排序时默认按first升序也完全够用。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long target, capacity; int n; cin target capacity n; vectorpairlong long, long long stations; for (int i 0; i n; i) { long long pos, charge; cin pos charge; stations.push_back({pos, charge}); } stations.push_back({target, 0}); sort(stations.begin(), stations.end()); priority_queuelong long pq; long long battery capacity; long long cur 0; int cnt 0; for (auto [pos, charge] : stations) { battery - pos - cur; while (battery 0 !pq.empty()) { battery pq.top(); pq.pop(); cnt; } if (battery 0) { cout -1 \n; return 0; } if (pos ! target) { pq.push(charge); } cur pos; } cout cnt \n; return 0; }C版本有两个细节值得提一是for (auto [pos, charge] : stations)是C17的结构化绑定笔试平台一般支持二是每次读入量大时ios::sync_with_stdio(false); cin.tie(nullptr);可以明显提速别偷懒不写。4.3 Python版heapq小顶堆负数模拟大顶堆Python的heapq没有直接的大顶堆常规做法是存负数。也就是说push进去-charge取出来再取负。这个操作是这道题里最容易被写反的地方。import sys import heapq def solve(): data sys.stdin.buffer.read().split() if not data: return it iter(data) target int(next(it)) capacity int(next(it)) n int(next(it)) stations [] for _ in range(n): pos int(next(it)) charge int(next(it)) stations.append((pos, charge)) stations.append((target, 0)) stations.sort() max_heap [] battery capacity cur 0 cnt 0 for pos, charge in stations: battery - pos - cur while battery 0 and max_heap: battery -heapq.heappop(max_heap) cnt 1 if battery 0: print(-1) return if pos ! target: heapq.heappush(max_heap, -charge) cur pos print(cnt) if __name__ __main__: solve()Python这边一个实用经验是用sys.stdin.buffer.read().split()读取所有输入再转成整数比逐行input().split()快非常多在n10^5这种规模下差距是肉眼可见的。4.4 三版实现对比与踩坑清单语言堆容器核心注意点JavaPriorityQueueLong需Collections.reverseOrder()用long比较器别写b-a输入用BufferedReaderCpriority_queuelong long默认大顶堆用long longC17结构化绑定关同步流Pythonheapq默认小顶堆存负数负数入堆容易忘取负用sys.stdin.buffer.read()提速三个版本核心逻辑完全一致区别只在于不同语言对堆的默认行为不同。如果笔试现场时间紧我建议先用自己最熟的语言把思路跑通再考虑要不要换语言。毕竟这类题考的是模型识别不是语言拼写。5. 笔试现场的调试技巧与自测用例5.1 五个自测用例保证代码能AC笔试写完代码不要急着提交先用几组边界用例自测一下。下面这五组我觉得足够覆盖大多数问题建议直接拿来当“体检套餐”。用例编号输入期望输出考察目的110 6 42 3 / 4 4 / 5 5 / 8 21样例基本流程22 1 0-1满电也到不了无解310 10 00满电直接到不用充45 2 34 1 / 1 2 / 3 12站点乱序需要排序510 3 31 5 / 2 5 / 9 12一次充电量不够需要连续取堆重点说下用例5满电3到1号站剩2到2号站剩1此时要到9号站还差得远堆里有两次5电量可选先取一个5电量变4还是不够到9再取一个5电量变9足够开到9号站。这个用例专门验证while循环里“反复取堆直到电量非负”的逻辑非常容易漏。5.2 笔试现场的IO细节和调试习惯拼多多春招这类笔试通常用牛客或赛码平台需要自己处理标准输入输出。如果你的代码在本地IDE跑得好好的一提交就报超时多半是IO写法的问题。Java用Scanner在数据大时确实慢换BufferedReaderC别忘关同步流Python别用逐行input()。我自己笔试时的习惯是先在纸上把样例手算一遍确认输出再跑程序。手算过程能帮助你把“先欠着再反悔”的逻辑内化写代码的时候就不容易在堆的取出时机上犯错。另外如果你对某一版记忆不确定可以用暴力枚举来对拍。n小于等于10时直接枚举所有充电站组合看哪些组合能到达终点取最小次数和贪心代码的结果对比。暴力法虽然慢但验证小数据足够能快速发现堆逻辑写错了。5.3 想不通时回到“两个问题”检查法调了很多遍还是WA或者思路卡住时问自己两个问题我有没有把所有“路过但没充电”的站点充电量放进堆里我是不是在电量真正为负的时候才取堆而不是提前取这两个问题对应这道题的两个核心逻辑几乎90%的bug都出在这两处。我自己第一次写的时候就是把入堆写在了“判断是否充电”之前导致当前站点还没决定充不充充电量先变成了后备选项后续结果完全乱掉。这种错很难肉眼看出来对拍才能暴露。6. 变形题与延伸思考摸清这类题的出题套路6.1 变形一每个充电站有价格求最小充电费用如果题目改成“每个充电站充电价格不同求到达终点的最小总费用”贪心策略就要跟着改。此时堆里存的不是充电量而是“单位价格能买到的电量”或者说“性价比”。每次缺电时从已过站点里选价格最低的充电站补电本质上还是同一个“先欠着、撑不住再取”的框架只是堆的比较维度从“电量最大”变成“单价最低”。如果每个站只能充固定电量且只能充一次问题会更复杂可能要动态规划但笔试里主要考的还是上面版本。6.2 变形二判断能否在k次充电内到达多了一个限制参数k问能不能在不超过k次充电的前提下到达终点。这时候可以二分答案对充电次数上界做二分check函数用同一个堆逻辑只是限制cnt不能超过k。复杂度会多一个log但n10^5照样能跑。6.3 变形三有多个目标点需要顺序经过如果把题目改成“需要依次经过多个目标点”处理方式也很自然把每个目标点都当作一个强制经过的站点它们都不能作为充电点但会触发“电量不足检查”。本质上还是同一个循环结构只是终点列表变多了。这类扩展在美团、字节的笔试题里出现过值得留意。我个人判断这类“路径消耗 补充资源 最小补充次数”的题以后大概率还会以各种包装出现。与其背题不如把“延迟决策 大顶堆反悔”这套底层逻辑吃透换个场景照样能认出来。