企业官网建设流程全解析

凌晨两点，考研群里弹出一张截图，题目标题写着“To Fill or Not to Fi”——其实原题是浙大机试的经典题“To Fill or Not to Fill”，对应PAT甲级1033。截图下面跟着一串问题：为什么要在油价高的站加满？为什么不直接在起点灌一箱油走人？为什么我的代码样例能过，一提交就错？

这道题我前前后后刷了三遍，每次都能踩出新的坑。它表面是“汽车加油”的模拟题，实际考的是贪心策略的边界判断，而且坑点全藏在题目细节里，不是算法本身有多难。如果你准备浙大机试、保研机试，或者想刷PAT甲级，这道题几乎绕不开。今天我把整个决策逻辑、代码实现、易错点全部拆开讲一遍，争取让你看完能直接AC。

1. 先别急着写代码：题目背后的真实场景

1.1 场景还原：一次让人肉疼的自驾

想象你开车从杭州出发去另一个城市，目的地距离已知，车子油箱容量固定，每升油能跑的公里数也固定。沿途分布着若干个加油站，每个加油站的距离和油价都不一样。你希望用最少的钱到达终点，或者退一步说，如果油不够到终点，你要知道最远能开到哪里。

这听起来像生活里常见的“长途自驾加油策略”问题，但机试把它抽象成了几个冷酷的条件：

• 油箱容量是固定的，不能超容量加油；
• 每升油能跑的里程是固定的，不会因为你开得快或慢而变化；
• 每个加油站的油价可能不同，而且同一站你可以加任意数量的油，不要求加满；
• 你从起点出发时油箱是空的。

很多第一次做这道题的人会陷入一个误区：以为要动态规划，或者要模拟“每次看到加油站就加一点”。实际上题目给了一个非常重要的隐藏条件：油量是连续的，不是按“箱”或“桶”计算的。这意味着你可以精确地只加“刚好够开到下一站”的油量，也可以加满，甚至可以加一半。这个灵活性就是贪心策略能成立的基础。

1.2 输入输出里的隐藏规则

原题的输入格式长这样：第一行是四个数，分别代表油箱容量、每升油可行驶的距离、起点到终点的总距离、沿途加油站的数量。接下来若干行，每行是一个加油站的油价和它距离起点的位置。

这里有两个很容易忽略的规则，直接影响你的算法正确性：

第一，加油站列表不是按距离排序给你的，必须自己排序。我见过好几个人在这上面栽了跟头——题目描述里没有明确说“输入按距离递增”，但数据往往不是有序的，你得先按距离排序。

第二，如果起点处没有加油站，那车根本没法出发，要直接输出最大行驶距离0.00。这个边界很多人漏掉了，结果常见的评测用例过不了。

输出也有讲究：如果能到达终点，输出最小花费，保留两位小数，格式是“The minimum travel cost: XX.XX”；如果不能到达终点，输出“The maximum travel distance: XX.XX”。注意当无法到达终点时不需要输出花费，只要输出距离就行。

2. 贪心策略怎么定：三个核心决策

2.1 什么时候只加“够到下一站”的油

先把整道题的核心逻辑讲明白。你在当前加油站，手里有一个关键信息：当前油箱里还剩多少油，以及当前油价是多少。你接下来要做的决策是：加多少油，开到哪个加油站。

最直观的想法是：如果前面某个加油站油价更便宜，那我现在就应该少加点，只加够开到那个便宜加油站的油量，然后到那边再补油。因为同样的钱在那边能买更多油，我现在多加一升就亏一升。这个“少加”的极限就是“刚好够开到便宜站”，到了那儿油箱刚好见底或者还剩一点点，都不亏。

这个判断在代码里对应“在可达范围内找第一个价格低于当前价格的加油站”。注意是“第一个”，而不是“最便宜的那个”。为什么是第一个？因为假设当前站是A，前方有两个便宜站B和C，其中B比C更近。如果我能先到B，在B加油显然比从A带一大堆油跑到C更划算，因为A的油比B贵。所以只要前方出现第一个更便宜的站，就应该把目标定在那里，而不是越过它去更远的便宜站。

2.2 什么时候直接“加满”

反过来，如果前方所有能到达的加油站油价都比当前站贵，那情况就完全反过来了：当前站的油就是未来一段时间里最便宜的，此时应该尽可能多地买，也就是直接把油箱加满，然后开到前方可达范围内油价最低的那个站去。

这个“加满”的决策是整道题最反直觉的地方。很多人会觉得：既然下一站油价更贵，那我应该少加油，省着点。但实际上你省不了，因为你的车必须往前走，必然要在某个前方加油站加油，而那个站的油更贵。与其到时候用更贵的价格买油，不如现在用当前这个相对便宜的价格多买一些存着，相当于提前锁价。唯一的限制就是油箱容量，所以“多买”的上限就是加满。

这时候的下一步目标，是前方所有可达加油站里油价最低的那个，而不是最近的那个。因为你已经决定加满油了，油箱里装满了当前站的便宜油，接下来要尽量把这段便宜油用在更远的路程上，中途如果停在一个油价更贵的站加油，加的越少越好，因此优先开到油价最低的站去，把便宜油消耗掉一部分，再在相对不那么贵的站补油。

2.3 为什么这是全局最优：一个直觉证明

这个贪心策略的正确性，可以用一句话概括：每一段路程，你都在用你能买到的最便宜的油来跑。把整个行程看成若干段，每一段从当前站到下一个决策站。如果前方有更便宜的站，这一段用的油全部来自当前站，但量只控制到刚好够到便宜站，等于“不多花一分钱在贵油上”；如果前方没有更便宜的站，这一段用的油几乎全部来自当前站，因为当前站是接下来一段时间内最便宜的，所以你尽可能灌满，让后面的贵油使用量最少。

从全局看，这就像是一个局部最优的累加。由于每次决策都只影响当前这一段路的用油来源，而下一段路又是在新的起点上重新做一个同样的选择，因此局部最优组合起来就是全局最优。这个逻辑和“区间调度”类贪心题很像，你不需要考虑遥远未来的复杂情况，只需要盯住当前油站和前方可达范围内的油价关系。

3. 完整演算：跟着跑一遍两个典型样例

3.1 样例一：能到达，抠出最少花费

为了把策略变成肌肉记忆，我手算一个具体例子。假设油箱容量50升，每升油能跑8公里，起点到终点总共500公里。加油站如下：

• 0公里处，油价6.00元；
• 100公里处，油价5.00元；
• 400公里处，油价7.00元。

终点在500公里处。

从0公里出发时，油箱是空的。满油状态下能跑50乘以8等于400公里，所以终点500公里不在当前可达范围内。在0公里到400公里这一段内，能找到的加油站有100公里处的油价5.00，比当前6.00便宜，于是决策是：只加刚好够到100公里的油。这段距离100公里，耗油100除以8等于12.5升，花费12.5乘以6等于75元。到100公里时，油箱基本见底。

到了100公里处，油箱剩余约0升。此时满油续航依然最多400公里，终点500公里刚好可到达。在100公里到500公里这个可达范围内，油价7.00比5.00贵，均不是更便宜的站；但终点距离500公里，耗费500减100等于400公里，耗油400除以8等于50升，恰好等于油箱容量。于是这里的最优决策是：加满50升，油价5.00，花费250元，然后一路开到终点，到终点时油箱正好空。总花费75加250等于325.00元。

注意中间有一个细节：如果我在0公里处多加点，比如加30升，虽然总油量更充裕，但到100公里时还剩17.5升，这时在100公里处只需要加32.5升而非50升，算下来总花费反而更高。原因就是0公里处的油价更贵，能不加就不加。

3.2 样例二：到不了，最远距离怎么算

再看一个无法到达终点的例子。假设油箱容量30升，每升油跑8公里，起点到终点450公里。加油站如下：

• 0公里处，油价7.00元；
• 100公里处，油价6.00元；
• 200公里处，油价8.00元。

从0公里出发，满油可跑30乘以8等于240公里，显然到不了450公里。在0公里到240公里范围内，100公里处油价6.00比7.00便宜，所以只加刚好到100公里的油：12.5升，花费87.5元。

在100公里处，满油续航240公里，能到340公里，依然到不了450公里。前方加油站是200公里处油价8.00，比当前6.00贵，没有更便宜的站，所以决策是加满油箱。当前油箱余量大约是0升，加满30升需要花费180元。从100公里开到200公里耗油100除以8等于12.5升，到200公里时油箱剩余17.5升。

在200公里处，满油续航依然是240公里，最远能到440公里，而终点450公里仍然差10公里，到不了。前方没有加油站了，此时只能把油箱加到满。油箱现在有17.5升，容量30升，所以最多只能再加12.5升，花费12.5乘以8等于100元。加满后，从200公里处还能跑240公里，到达440公里处油尽。因此输出最远距离440.00公里，不输出花费。

这个例子提醒我们：判断能否到达终点，不是看“当前加油站的油价是否比终点便宜”，而是要看当前位置加满油后能否覆盖终点距离。终点是否可达，决定了它能不能被当成一个“0元加油站”参与决策。

3.3 从演算提炼成状态机

两个例子跑完，可以把决策逻辑整理成一张状态表：

最后一行可能有人不理解：明明终点更近，为什么不直接开到终点？因为只要终点可达，且“终点”可以视为0元加油站，那么在决策逻辑里，终点就是“前方第一个比当前油价低的站”，自然会被选中，于是过渡到“只加刚好到终点的油”。所以状态表其实可以进一步统一为：始终在当前站的满油可达范围内，找第一个价格低于当前站的站点，如果找到，就只加够到那里的油；如果找不到，则加满并开往可达范围内价格最低的站点。

4. 代码实现的关键细节

4.1 把“终点”也当成一个加油站

代码实现里最优雅的一个技巧，是在加油站数组末尾插入一个特殊站点：距离等于总距离，油价等于0。这么做有两个好处。

第一，让“终点可达”这件事自动融入贪心判断。终点油价为0，任何正整数油价都比它高，所以一旦终点落在当前站的满油可达范围内，它必然成为“第一个比当前站更便宜的目标”，代码就会自动走到“只加刚好到终点的油”这个分支，不需要单独写if。

第二，避免在循环里反复判断“我现在能不能直接到终点”。你只需要把这个哨兵站点当成普通站点处理，排序后它自然会出现在正确的位置。

不过要注意，终点的油价虽然是0，但它没有“再往前开”的属性。如果当前站加满油也够不到终点，那么终点就不会出现在可达范围内，代码自然转向“加满开往最低价站”的分支，接下来如果没有任何真实加油站可选，就意味着无法到达终点，这时直接输出最远距离即可。

4.2 油的存量、花费与浮点精度

写代码时最容易出问题的变量有三个：当前剩余油量、当前累计花费、当前所在加油站下标。很多人喜欢用“到达某站时油量恰好为0”来简化，但实际贪心过程中，有时候到达中间站时油箱里还有油，比如上一站加满后开到下一站，只消耗了一部分。

维护剩余油量的标准做法是：

• 记录当前油量curOil；
• 当决定从当前站开往目标站，先算出两站距离distance，再算出这段路需要的油量need = distance / unit；
• 如果curOil大于等于need，说明不用在当前站加油，直接消耗存量开过去，curOil -= need；
• 如果curOil小于need，在当前站补油，补油量add = need - curOil，花费add * price，然后curOil = 0。

浮点精度是这道题的另一大坑。题目要求保留两位小数，但中间计算如果直接用浮点数反复加减，可能出现99.999999、0.000001之类的误差。建议所有浮点数比较都不用==，而是用差值小于1e-8来判断；最后输出时用printf("%.2f")，大多数评测系统会接受合理误差，但如果你在比较“两个价格是否相等”时用了==，遇到边界数据就容易崩。

4.3 几个常见实现坑

我整理一下自己踩过和帮别人debug时遇到的高频问题，按出现频率排序：

坑一：起点没有加油站。如果排序后第一个加油站的distance不为0，说明车根本没油可加，直接输出最大行驶距离0.00。这个分支一定要写在最前面。

坑二：可达范围内找不到任何站点。当当前站加满油也够不到下一个真实加油站时，说明前路断了。此时输出的是“从起点到当前站最远能到哪”，而不是0也不是当前站距离。具体来说，最远距离应当是“当前站距离 + 当前剩余油量 + 当前站补满油后的总续航”，但要注意油箱容量限制，不能无中生有。

坑三：排序后没把终点插进去。这个会导致终点可达时没有站点可选，程序会在循环里越界或者死循环。一定要记得在排序前或排序后把终点作为最后一个哨兵加入数组。

坑四：油价比较用大于等于。如果前方站点价格等于当前站价格，把它当作“不贵于当前”而不是“贵”，通常能省一点事，因为等价的油在更远处加，不改变总花费，还能少停一次。不过两种写法都能过，关键是逻辑要自洽。

我给出一段可参考的核心循环骨架，用到的是C++风格，但逻辑和语言无关：

sort(stations.begin(), stations.end(), cmp); stations.push_back({D, 0.0}); // 哨兵 double curOil = 0.0, cost = 0.0; int cur = 0; while (cur < stations.size() - 1) { int next = -1; double minPrice = INF; bool foundCheaper = false; // 在当前站满油可达范围内寻找目标 for (int i = cur + 1; i < stations.size(); i++) { double dist = stations[i].dist - stations[cur].dist; if (dist > capacity * unit) break; if (stations[i].price < stations[cur].price) { next = i; foundCheaper = true; break; } if (stations[i].price < minPrice) { minPrice = stations[i].price; next = i; } } if (next == -1) { // 到不了任何站 double maxDist = stations[cur].dist + capacity * unit; printf("The maximum travel distance = %.2f\n", maxDist); return 0; } double distNeed = stations[next].dist - stations[cur].dist; double needOil = distNeed / unit; if (foundCheaper) { // 只加刚好到 next 的油 if (curOil < needOil) { cost += (needOil - curOil) * stations[cur].price; curOil = needOil; } curOil -= needOil; } else { // 加满，开往最低价站 cost += (capacity - curOil) * stations[cur].price; curOil = capacity - needOil; } cur = next; } printf("The minimum travel cost = %.2f\n", cost);

这段代码里的foundCheaper对应“前方第一个更便宜站”，next在未找到更便宜站时记录的是可达范围内油价最低的站。有个细节值得注意：在foundCheaper分支里，如果当前油量已经够开到下一站，那就不需要补油；在else分支里，加满后开到下一站，剩余油量要记得减去消耗。这段逻辑我建议自己多推演几遍，纸上谈兵很容易漏掉curOil的正确更新。

5. 常见问题与调试实录

5.1 问题速查表

把常见的坑汇总成一张表，平时复习直接翻这一页就够了。

5.2 给准备机试同学的几句实话

这类“加油站贪心”题，在PAT甲级和浙大机试里属于中频考点，难度不算顶，但区分度很高。每年都有不少人样例都能跑通，一交就挂在边界上。我个人的刷题建议是：不要满足于“把代码写出来”，而是把每个分支都自己构造一个极端用例。

比如你可以构造“油箱很大但油价递减”的样例，验证自己是否每一步都只加刚好够到下一站；再构造“油箱很小但油价递增”的样例，验证自己是否每次都加满；最后构造一个“中间有一段路没有任何加油站”的样例，验证最远距离计算是否处理了油箱存量。

另外，机试现场时间紧张，不要一上来就写代码。先把题目里的输入输出规则用中文写一遍，把各种边界列出来，再动手。这道题如果理解了贪心框架，正常写下来应该能在半小时内完成，但如果你一上来就陷入“模拟每一公里”的思路，很容易写出一堆if-else还不对。

最后再分享一个小技巧：我每次复习这道题，都会先用纸笔把决策状态表画出来，再对照代码逐行看。状态表理顺了，代码里的浮点、边界、哨兵这些细节自然就清晰了。贪心题最怕的不是不会贪，而是你明明贪对了，却被一个边界条件卡到怀疑人生。希望这篇拆解能帮你少走几次弯路。