洛谷P1016《旅行家的预算》绝对算得上贪心算法入门的一道经典老题。题目不长但每次看题解区都能看到有人卡在No Solution的判定上或者被浮点精度坑到怀疑人生。我当年第一次刷这题的时候也是写了好几个版本才真正跑通今天就把完整的思路和代码重新整理一遍尤其是那些题解里不会特意点破的细节。这题说的是一个旅行家开车从起点到终点油箱容量有限沿途每个加油站的油价还不一样问怎么加油总花费最少。听起来像日常自驾游的省钱攻略实际上是一个带容量约束的“最低成本补给决策”问题。不管你是刚刷到这道题的新手还是想复习贪心策略的老玩家这篇都能给你一个可以直接抄走、又能讲清楚原理的答案。1. 先把题目翻译成“计算机能算的东西”1.1 题面到底在说什么题目会给你一组数据起点到终点的总距离是 D1汽车油箱容量是 C 升每升油能跑 D2 公里起点加油站每升油的价格是 P沿途一共有 N 个加油站。接下来 N 行每行给出第 i 个加油站离出发点的距离 Di 和每升汽油的价格 Pi。注意一个最容易看反的点D2 的单位是公里每升不是百公里油耗。也就是说满油状态下汽车最多能跑C × D2公里这个值我习惯叫它maxRun后面所有可达性判断都是围绕它展开的。如果汽车因为油不够中途到不了任何一个加油站或者到不了终点那就输出No Solution。否则输出最小加油花费保留两位小数。1.2 把变量和约束整理成一张表我刷题的习惯是先建模把每个变量到底是什么、单位是什么、边界是什么搞清楚不然写着写着就容易混。变量含义单位D1起点到终点的总距离kmC油箱容量LD2每升油可行驶的距离km/LP起点油价元/LN中间加油站数量个dis[i]第 i 个加油站离起点距离kmprice[i]第 i 个加油站油价元/LmaxRun满油最大续航 C × D2km这道题有一个非常经典的建模技巧把终点也当成一个加油站它的距离是 D1油价是 0。这样做的好处是最后一段路程也能统一用“前方有没有更便宜的加油站”这个逻辑去处理。终点油价是 0只要终点在可达范围内贪心策略会自动选择“只加够到终点的油”不会傻乎乎地在最后一个加油站加满。还有一个隐含条件汽车一开始油箱是空的所以出发点必须加油否则连第一个加油站都到不了。1.3 为什么“我全加满”和“我只在最便宜的站加油”都不行我第一次做这道题的时候第一反应是“既然油价不同那我每次都把油箱加满总不会错”。但仔细一想就发现不对如果你在起点加满开到后面遇到一个油价更低的加油站时油箱里还堆着一堆已经买贵的油相当于明明有便宜的油摆在面前你却因为油箱没空位而装不进去。反过来如果有人想“我只在全程油价最便宜的那个加油站加油”这也有问题。一个是油箱容量有上限你可能根本开不到那个最便宜的站就熄火了另一个是如果最便宜的站在很前面你加满也只能覆盖一段路后面还是要以更贵的价格补油。所以正确的思路不是“哪个站便宜就去哪个站”而是站在当前加油站只考虑在满油续航范围内能到的那些加油站做一个短视但足够聪明的选择。这也是贪心算法在这道题里能跑通的核心原因。2. 贪心策略的核心两条规则走天下2.1 站在当前加油站时的两个选择假设你现在站在第 i 个加油站手上有一些剩余油量油箱容量为 C前方满油能跑maxRun公里。这时候你只需要问自己两个问题第一在满油可达范围内是否存在一个加油站它的油价低于当前加油站如果存在那就只买“刚好能开到那个更便宜加油站”的油然后立刻出发。因为前方既然有更便宜的油当前这一站的油能少买就少买只要够过路就行。第二如果满油可达范围内没有任何加油站比当前油价低说明当前站就是这个局部范围内最便宜的地方。这时候果断把油箱加满因为前方再怎么加油都比这里贵现在能多囤一点便宜油就多囤一点。然后从可达范围内挑一个油价最低的加油站作为下一站继续重复这个过程。这两条规则就是我最终代码的核心。很多题解喜欢把第二条说成“加满后去最便宜的站”但容易漏掉第一条里的一个关键细节这个细节下面单独讲。2.2 重点找的是“第一个更便宜的站”不是“最便宜的站”很多初写这题的人会卡在一个地方既然要找更便宜的加油站那我直接扫描整个满油可达范围找油价最低的那个不就行了吗为什么要强调“第一个更便宜的”原因是如果只往后找价格最低的那个站可能会忽略一个更优的选择你不需要一口气开到最便宜的那个站点你只需要开到“第一个比你当前油价便宜的站点”就够了。举个例子。当前加油站油价是 5 元/升前方有两个站都可达A 站距离 50 公里油价 4.9 元/升B 站距离 90 公里油价 1 元/升每升油能跑 10 公里。如果直接去 B 站从当前站出发需要加 9 升油每升 5 元光这一段就要 45 元。如果先去 A 站只需要加 5 升油花费 25 元到了 A 站再加油虽然 A 站油价 4.9 元也没便宜太多但后面 40 公里所需的 4 升油变成了 4.9 元/升总共 44.6 元比直接冲 B 站还省一点。所以算法里要做的不是“在可达范围内找最便宜的”而是从当前站往后扫描找到第一个油价低于当前油价的站只要这个站可达就把它作为目标。如果一直找不到才进入“当前站就是局部最低价”的加满分支。2.3 为什么这两条规则能凑出全局最优贪心算法最怕的是“局部最优不等于全局最优”但这道题恰好是一个例外原因可以用一句话概括每一段路最终消耗的油量是固定的。从起点到终点无论你怎么安排加油策略总耗油量都是D1 / D2升每一升油都对应一段具体的路程。所谓最优方案本质上就是决定“每一段路程消耗的油到底是在哪一站买的”。第一条规则保证了如果前方有便宜的油当前站这桶贵油只覆盖到那个便宜站之前的必要路段绝不浪费一公里在更贵的油上。第二条规则保证了如果当前站已经是可达范围内的最低价那么在这片区域里所有需要的油都应该尽可能从当前站买加满就等于买了尽可能多的“低价油”带走。把这两条规则一路循环下去每一段路程的用油都落在了它能触达的“最低价加油站”整体当然就是最优的。这比用动态规划去枚举所有状态要清爽得多。2.4 策略分支速查表当前位置情况动作原因满油可达范围内存在更低油价站只加到刚好能到该站的油量直接出发前方有更便宜的油当前站能少买就少买满油可达范围内没有任何更低油价站加满油箱再选择可达范围内油价最低的站作为下一站当前站是这个局部区域里最便宜的多买多带终点在满油可达范围内会被判定为“油价为0的更便宜站”只加够到终点的油终点价格最低没必要在沿途多买这张表就是整道题最核心的决策逻辑代码只是把它翻译成循环而已。3. 从策略到代码手写一份可提交的Java实现3.1 预处理虚拟终点和No Solution检测我先把所有加油站读进来包括起点在内一起放进一个列表里然后手动加入终点站。输入数据一般已经按距离排序但保险起见还是按距离重新排一下。接着做一次全局检查任意相邻两个站之间的距离大于maxRun说明即使你在前一个站把油箱加到满也不可能开到后一个站那就直接输出No Solution。这一步非常关键而且放在预处理里做最省心。否则后面在主循环里每次都要判断“下一个可达站是否存在”既啰嗦又容易漏边界。3.2 主循环设计两个分支都要照顾到剩余油量循环逻辑可以概括成三步第一步从当前站往后扫描在满油可达范围内找第一个price[j] price[pos]的站点。第二步如果找到了计算从当前站到目标站需要的油量need对比当前剩余油量curOil。如果剩余油不够就补到刚好够如果剩余油已经够那就一滴油都不用加。接着让curOil - need把当前站指针移动到目标站。第三步如果没找到说明当前站是局部最低价。先加满油然后从可达范围内找一个油价最低的站作为下一站。这里要特别注意加满之后开到下一站油箱里还会剩下不少油这个剩余油量是之前买的便宜油要留着继续用。3.3 完整Java代码下面这份代码我在洛谷上测过可以直接提交类名记得改成Main。import java.util.*; public class Main { static class Station { double dis; double price; Station(double dis, double price) { this.dis dis; this.price price; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); double D1 sc.nextDouble(); double C sc.nextDouble(); double D2 sc.nextDouble(); double P sc.nextDouble(); int N sc.nextInt(); ListStation stations new ArrayList(); stations.add(new Station(0, P)); for (int i 0; i N; i) { double d sc.nextDouble(); double p sc.nextDouble(); stations.add(new Station(d, p)); } // 把终点当作一个油价为0的加油站 stations.add(new Station(D1, 0.0)); sc.close(); // 防止输入乱序按距离排序 stations.sort(Comparator.comparingDouble(s - s.dis)); double maxRun C * D2; double eps 1e-9; // 相邻站点距离超过满油续航直接无解 for (int i 1; i stations.size(); i) { double gap stations.get(i).dis - stations.get(i - 1).dis; if (gap maxRun eps) { System.out.println(No Solution); return; } } int n stations.size(); int pos 0; double curOil 0; double cost 0; while (pos n - 1) { Station cur stations.get(pos); // 分支1在满油可达范围内找第一个更便宜的加油站 int cheaperId -1; for (int j pos 1; j n; j) { double gap stations.get(j).dis - cur.dis; if (gap maxRun eps) { break; } if (stations.get(j).price cur.price - eps) { cheaperId j; break; } } if (cheaperId ! -1) { // 只加到能到达更便宜加油站的油量 double need (stations.get(cheaperId).dis - cur.dis) / D2; if (curOil need - eps) { double add need - curOil; cost add * cur.price; curOil need; } curOil - need; if (curOil 0) curOil 0; pos cheaperId; } else { // 分支2没有更便宜的站加满然后去可达范围内油价最低的站 double add C - curOil; cost add * cur.price; curOil C; int nextId -1; double minPrice Double.MAX_VALUE; for (int j pos 1; j n; j) { double gap stations.get(j).dis - cur.dis; if (gap maxRun eps) { break; } if (stations.get(j).price minPrice - eps) { minPrice stations.get(j).price; nextId j; } } // 理论上不会出现因为预处理已经保证相邻站可达 if (nextId -1) { System.out.println(No Solution); return; } double need (stations.get(nextId).dis - cur.dis) / D2; curOil - need; if (curOil 0) curOil 0; pos nextId; } } System.out.printf(%.2f\n, cost); } }3.4 手算一个小样例把逻辑走通我习惯用一组自己随便编的简单数据来做验证口算就能算明白总距离 D1 100 公里油箱容量 C 10 升每升油能跑 D2 10 公里起点油价 P 5 元/升中间加油站数量 N 1该站距离起点 50 公里油价 4 元/升满油续航maxRun 10 × 10 100公里。从起点出发时油箱是空的。站在起点往后扫描加油站 1 油价 4 元低于起点油价 5 元而且距离 50 公里在满油续航内。于是进入分支1只加“刚好到加油站1”的油量50 / 10 5升花费5 × 5 25元。到达加油站1时油箱油量正好是 0。再站在加油站1往后扫描终点距离 50 公里油价是 0显然比 4 元便宜而且可达。于是只加到终点的油量50 / 10 5升花费5 × 4 20元。总花费 45 元。如果换一种方案在起点直接加满 10 升花费 50 元开到加油站1时油箱还剩 5 升终点刚好不需要再加油总花费反而更贵。从这个例子能直观看出“只加到能开到的下一个更便宜站点”确实能省钱。4. 常见问题与排查技巧实录4.1 精度问题double的误差能卡掉一整个下午这题所有数据都是小数用double是肯定的。但要小心两点。第一比较两个数大小时不要用或直接抠死。代码里我用了一个eps 1e-9判断“油价更低”要写成price[j] cur.price - eps判断“距离超过续航”要写成gap maxRun eps。否则一些极端数据会出现错误的边界判断。第二扣油量时可能出现负的-0.000000001这不是真的数学错误而是浮点存储误差。我在curOil - need后面加了一句if (curOil 0) curOil 0把这种误差直接抹掉。这一招虽然看起来粗暴但很实用。4.2 No Solution的判断究竟是预处理管够还是循环里也要兜底我的做法是预处理检查相邻站点距离只要有一个相邻间距超过满油续航就直接输出无解。这样可以提前跳出逻辑也简单。但有些写法是在主循环里找“下一个可达站”找不到就输出无解。两种都能过不过我觉得预处理更清晰它把“能不能开过去”这个硬条件一次性检查干净主循环里就不用反复担心“无解”的问题。4.3 加油量、剩余油量的更新顺序千万别搞反这是很多初版代码的致命伤。在分支1里正确顺序是先计算需要的油量再对比当前剩余油量决定加多少油加完之后用新的curOil减去这段路程消耗的油量得到到达下一站时的剩余油量。如果顺序写反了比如先减距离耗油再去判断加油量就会出现油箱油量不够却还在硬开的情况最终答案直接出错。4.4 常见问题速查表症状原因解决办法答案比预期少很多中途某段路没有计入油价为0的终点确认终点是否加入站点列表输出No Solution但手动模拟有解预处理时用了而不是 eps浮点比较统一加eps答案比预期多每次到站都加满油检查是否在分支1中加了过多油保留两位小数输出格式不对用了println输出日志使用printf(%.2f, cost)我自己最推荐的习惯是写完代码之后不要急着提交先拿一个手算样例跑一遍再故意造一个“中间某段路距离大于满油续航”的无解样例确认能准确输出No Solution。这两关过了基本就稳了。5. 从一道题看一类“加油站贪心”问题5.1 这类问题的共同特征P1016看起来是个题实际上背后是一类非常有实际意义的模型你有若干个价格不同的补给点你的“随身容量”有限要从起点到终点如何设计购买策略让总成本最低。类似的问题还有“带油罐头走沙漠”“仓库补货规划”“云资源包购买时机”等。一旦看懂这题的贪心逻辑很多变体都能直接套用。核心永远是那两条前方有便宜货就只准备到便宜货位置的量前方没有便宜货就在当前尽可能囤满。5.2 如果站点数量很大当前写法够用吗洛谷这题的 N 非常小O(N^2) 的扫描完全足够了。但如果把 N 放大到十万甚至百万那每次都在可达范围内扫描一遍显然不现实。这时候可以用双向链表加单调栈的经典优化把站点按油价维护成一个单调结构然后在滑动窗口内快速找最值。不过那就是另一个层面的话题了P1016这个数据范围根本不需要我建议你先把普通贪心写熟再考虑优化。5.3 也能用动态规划或最短路来理解如果贪心证明让你觉得不够踏实可以换个角度想把每一个加油站当成一个节点只要两个节点之间的距离不超过maxRun就从前一个节点向后一个节点连一条边边的代价就是“为了从这一段通过需要在出发站买多少油”。这样整个问题就变成了一个带权图的最短路问题理论上可以用 Dijkstra 解。不过实际上因为这是一条线性的路而且油价满足特定的局部关系贪心比最短路更直观、更快。我的建议是刷题阶段先把贪心吃透动态规划思路可以作为理解辅助不用真写成 DP 提交。最后再分享一个我自己的小习惯做这类求最小费用的模拟题第一步永远是把所有站点画在一根时间轴上标上油价然后在脑内驱动那辆车走一遍。只要手动模拟能走通代码里每一步都会有明确含义。P1016的难点从来不是算法本身而是你愿不愿意把“当前油价”和“满油可达范围”这两个状态时刻记在心里。把这两个状态搞顺了这题从此就是一道送分题。