凌晨两点考研群里弹出一张截图题目标题写着“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前方有更便宜站只加刚好到该站的油当前油站出发前方无更便宜站终点不可达加满开往可达范围内油价最低站当前油站出发前方无更便宜站终点可达只加刚好到终点的油当前油站出发前方有更便宜站且终点可达仍只加刚好到该便宜站的油不必考虑终点最后一行可能有人不理解明明终点更近为什么不直接开到终点因为只要终点可达且“终点”可以视为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 问题速查表把常见的坑汇总成一张表平时复习直接翻这一页就够了。现象原因解决办法样例过提交全错起点加油站距离不为0时没处理排序后检查第一个站点距离不为0直接输出0.00输出距离比正确答案大在“加满后开往最低价站”时错误地认为当前油量是0正确维护curOil加满后要减掉这段路程消耗死循环或数组越界没把终点作为哨兵加入数组在排序后push一个距离为D、油价为0的站点答案差0.01或0.1浮点精度比较出错价格比较用而非最终输出用printf保留两位小数能到达时输出了距离没区分“能到达”和“不能到达”循环正常跑完到终点则输出花费中途无站点可去则输出距离后return5.2 给准备机试同学的几句实话这类“加油站贪心”题在PAT甲级和浙大机试里属于中频考点难度不算顶但区分度很高。每年都有不少人样例都能跑通一交就挂在边界上。我个人的刷题建议是不要满足于“把代码写出来”而是把每个分支都自己构造一个极端用例。比如你可以构造“油箱很大但油价递减”的样例验证自己是否每一步都只加刚好够到下一站再构造“油箱很小但油价递增”的样例验证自己是否每次都加满最后构造一个“中间有一段路没有任何加油站”的样例验证最远距离计算是否处理了油箱存量。另外机试现场时间紧张不要一上来就写代码。先把题目里的输入输出规则用中文写一遍把各种边界列出来再动手。这道题如果理解了贪心框架正常写下来应该能在半小时内完成但如果你一上来就陷入“模拟每一公里”的思路很容易写出一堆if-else还不对。最后再分享一个小技巧我每次复习这道题都会先用纸笔把决策状态表画出来再对照代码逐行看。状态表理顺了代码里的浮点、边界、哨兵这些细节自然就清晰了。贪心题最怕的不是不会贪而是你明明贪对了却被一个边界条件卡到怀疑人生。希望这篇拆解能帮你少走几次弯路。