企业官网建设流程全解析

洛谷P1016《旅行家的预算》绝对算得上贪心算法入门的一道经典老题。题目不长，但每次看题解区都能看到有人卡在No Solution的判定上，或者被浮点精度坑到怀疑人生。我当年第一次刷这题的时候，也是写了好几个版本才真正跑通，今天就把完整的思路和代码重新整理一遍，尤其是那些题解里不会特意点破的细节。

这题说的是一个旅行家开车从起点到终点，油箱容量有限，沿途每个加油站的油价还不一样，问怎么加油总花费最少。听起来像日常自驾游的省钱攻略，实际上是一个带容量约束的“最低成本补给决策”问题。不管你是刚刷到这道题的新手，还是想复习贪心策略的老玩家，这篇都能给你一个可以直接抄走、又能讲清楚原理的答案。

1. 先把题目翻译成“计算机能算的东西”

1.1 题面到底在说什么

题目会给你一组数据：起点到终点的总距离是 D1，汽车油箱容量是 C 升，每升油能跑 D2 公里，起点加油站每升油的价格是 P，沿途一共有 N 个加油站。接下来 N 行，每行给出第 i 个加油站离出发点的距离 Di 和每升汽油的价格 Pi。

注意一个最容易看反的点：D2 的单位是公里每升，不是百公里油耗。也就是说，满油状态下汽车最多能跑C × D2公里，这个值我习惯叫它maxRun，后面所有可达性判断都是围绕它展开的。

如果汽车因为油不够，中途到不了任何一个加油站，或者到不了终点，那就输出No Solution。否则输出最小加油花费，保留两位小数。

1.2 把变量和约束整理成一张表

我刷题的习惯是先建模，把每个变量到底是什么、单位是什么、边界是什么搞清楚，不然写着写着就容易混。

这道题有一个非常经典的建模技巧：把终点也当成一个加油站，它的距离是 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 策略分支速查表

这张表就是整道题最核心的决策逻辑，代码只是把它翻译成循环而已。

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(); List<Station> 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 常见问题速查表

我自己最推荐的习惯是：写完代码之后，不要急着提交，先拿一个手算样例跑一遍，再故意造一个“中间某段路距离大于满油续航”的无解样例，确认能准确输出No Solution。这两关过了，基本就稳了。

5. 从一道题看一类“加油站贪心”问题

5.1 这类问题的共同特征

P1016看起来是个题，实际上背后是一类非常有实际意义的模型：你有若干个价格不同的补给点，你的“随身容量”有限，要从起点到终点，如何设计购买策略让总成本最低。类似的问题还有“带油罐头走沙漠”“仓库补货规划”“云资源包购买时机”等。

一旦看懂这题的贪心逻辑，很多变体都能直接套用。核心永远是那两条：前方有便宜货，就只准备到便宜货位置的量；前方没有便宜货，就在当前尽可能囤满。

5.2 如果站点数量很大，当前写法够用吗

洛谷这题的 N 非常小，O(N^2) 的扫描完全足够了。但如果把 N 放大到十万甚至百万，那每次都在可达范围内扫描一遍显然不现实。

这时候可以用双向链表加单调栈的经典优化：把站点按油价维护成一个单调结构，然后在滑动窗口内快速找最值。不过那就是另一个层面的话题了，P1016这个数据范围根本不需要，我建议你先把普通贪心写熟，再考虑优化。

5.3 也能用动态规划或最短路来理解

如果贪心证明让你觉得不够踏实，可以换个角度想：把每一个加油站当成一个节点，只要两个节点之间的距离不超过maxRun，就从前一个节点向后一个节点连一条边，边的代价就是“为了从这一段通过，需要在出发站买多少油”。这样整个问题就变成了一个带权图的最短路问题，理论上可以用 Dijkstra 解。

不过实际上，因为这是一条线性的路，而且油价满足特定的局部关系，贪心比最短路更直观、更快。我的建议是：刷题阶段先把贪心吃透，动态规划思路可以作为理解辅助，不用真写成 DP 提交。

最后再分享一个我自己的小习惯：做这类求最小费用的模拟题，第一步永远是把所有站点画在一根时间轴上，标上油价，然后在脑内驱动那辆车走一遍。只要手动模拟能走通，代码里每一步都会有明确含义。P1016的难点从来不是算法本身，而是你愿不愿意把“当前油价”和“满油可达范围”这两个状态时刻记在心里。把这两个状态搞顺了，这题从此就是一道送分题。