第一次在浙大机试真题清单里看到 To Fill or Not to Fill 这个题目名我先是会心一笑——这明显是拿《哈姆雷特》那句 To be or not to be 在玩梗。但等真正动手写代码我才发现这个加满还是不加满的决策远没有名字那么轻松。这是一道非常经典的贪心算法题核心场景很朴素你开车从杭州出发去目的地全程 D 公里油箱容量 C 升每升油能跑 D_avg 公里出发时油箱是空的。沿途有 N 个加油站每个站报两个数油价和离起点的距离。题目问终点到不到得了到得了的话最少要花多少钱到不了的话最远能开到哪一句话概括这就是一个油箱限量、价格不一、只能单向行进条件下的增量购买决策问题。它考察的不是背模板的能力而是能不能把生活里的加油直觉翻译成一套严密可执行的决策规则。浙大机试把它当作常客一点都不奇怪。这篇文章我会从题目建模讲起给出一份可以直接跑通核心逻辑的 C 实现再把我反复折腾这道题时踩过的坑、排查思路全部摊开来讲。无论你是准备浙大机试、PAT 甲级还是单纯想练贪心算法这篇内容都能让你少走不少弯路。1. 题目在问什么一个加油博弈的完整建模1.1 先把输入输出格式钉死这种题最怕的是题目都读歪了。标准输入是四个参数打头C油箱容量单位升浮点数D起点到终点的总路程公里浮点数D_avg每升油能跑的距离公里/升浮点数N沿途加油站数量整数接下来 N 行每行两个浮点数price 和 distance分别代表该加油站每升油价以及它离起点的距离。输出分两种情况能到终点就输出最少花费保留两位小数不能到终点就输出一行The maximum travel distance X.XX其中 X.XX 是最远能开到的距离同样保留两位小数。有个细节值得注意输入里可能出现 distance 大于 D 的加油站也就是设在目的地方向更远处的站。这种站对决策完全没有影响因为车一旦到了终点问题就结束了终点之后的价格再便宜也跟你无关。最稳妥的做法是在算法里直接把扫描范围限制到 D天然忽略它们。1.2 为什么这是贪心而不是动态规划判断一道题该用贪心还是动态规划先看它的状态转移有没有回退的可能。在这道题里车始终向前开走过的加油站不可能掉头回去再买油这是一个单向不可逆的过程。你在当前站做决策时只需要考虑前方满油可达范围内的站而不需要考虑已经过去的站。这个选择面只向前方展开的结构是贪心算法最舒服的舞台。那为什么不能直接无脑看到便宜就加满因为油箱容量有限你在一个便宜站加满油不代表你一定能撑到下一个便宜站你在一个贵站少加油也不代表后面就一定有便宜站等着你。你当前加的每一升油决定了你未来能覆盖多远的选择面本质是用现在的购买量去够未来的价格信息。真正合理的策略必须把当前油价和前方所有站点的价格放在一起比较。1.3 这道题真正在考什么浙大机试选拔的是工程能力而不是背书能力这道题恰好把几个关键维度全部覆盖到了边界条件处理起点没有加油站怎么办终点和起点重合怎么办某站距离恰好等于满油行驶上限怎么办浮点数精度钱和里程都要保留两位小数全程计算必须用 double用 float 很容易在某些测试数据上差出 0.01。逻辑闭环能不能把能到达和不能到达两条路径收进同一套循环逻辑里干净地终结而不是到处塞特判。说白了机试拼的就是你在有限时间内把一道表面简单、处处有暗坑的题写对的功力。2. 贪心策略把要不要加油变成三条铁律2.1 三条决策规则的完整表述我最初做题时的直觉是便宜就多加贵就少加但这句话太模糊直接落地必挂。经过反复推导真正可靠的策略被我收敛成三条规则按优先级排列规则一在当前站加满油能到达的范围内找第一个油价低于当前站的站点按距离从近到远看。只要找到就只买到刚好够开到那个站的油然后开过去。规则二如果范围内没有任何一个站比当前站便宜说明当前站是这一小段路上的价格洼地那就加满油然后开向范围内油价最低的站如果最低价有好几个去最近的那个。规则三如果范围内一个加油站都没有说明车已经走到极限最大行驶距离就是当前站距离加上满油可行驶距离。三条规则本身不复杂复杂的是为什么它们是对的以及边界情况怎么不写崩。2.2 为什么规则一要第一个更便宜而不是最便宜这是整道题最核心的逻辑点我第一次就栽在这里。假设你在当前站 A油价 8 元满油能跑 500 公里。前方 100 公里处有 B 站油价 7 元前方 300 公里处有 C 站油价 6 元。该去哪直觉会告诉你去 C因为 C 最便宜。但算笔账就明白了如果直接从 A 去 C需要在 A 买 300 公里对应油量。按每升跑 10 公里算就是 30 升乘以 8 元一共 240 元。如果先去 B在 A 只需要买 100 公里对应油量10 升80 元到了 B 再做下一步决策。显然先去 B 更优因为你最大限度压缩了在贵站买油的量把决策点提前推给了更便宜的站。所以规则一的准确措辞是第一个比当前站便宜的站不是范围内最便宜的站。只要前方存在任意一个更便宜的站就应该只买到刚好能够到它多买一升当前站的贵油都是亏的。2.3 为什么规则二要加满还要去最便宜的站反过来看规则二如果当前站加满油能到达的范围内所有站的油价都大于等于当前站说明当前站就是这段路的价格洼地。此时最优策略当然是趁便宜多买——直接加满。加满之后去哪去可达范围内油价最低的那个站逻辑和规则一是对称的既然未来所有站都比现在贵下一站当然优先挑最便宜的先落脚。如果两个站价格相同去更近的那个因为开到近站消耗的油更少到站后油箱里剩的油更多这个状态永远不会让后续决策变差。三条规则合在一起就是一个完备的闭环只要有路可走就把贵油的购买量压到最低一旦无路可走就停在原地报告最大行驶距离。2.4 终点直接可达其实是个陷阱很多流传的题解会在循环开头写一句特判如果终点在当前站加满油可达那就买到刚好到终点的油结束。这种写法在多数测试数据上能过但它在逻辑上并不严密。假设你在当前站油价 10 元前方 5 公里有个加油站卖 5 元终点在 100 公里外满油能跑 250 公里。终点直接可达会引导你在当前站买 20 升油直接跑到终点花 200 元。但正确做法是先花 1 升油的钱开到 5 公里外的便宜站到那里再买 19 升跑完剩下 95 公里总花费只有 105 元。所以我在代码里做了一个关键处理把终点虚拟成一个价格为 0 的加油站加入站点数组。这样一来终点可达不再是最高优先级的特判而是被规则一自然吸收——终点价格 0 永远低于任何真实油价只要终点在范围内规则一会自动判断要不要先去更近的便宜站中转一下。这个细节是我认为区分能 AC 的代码和逻辑真正严密的代码的分水岭。3. 代码实现一份可以直接跑通核心逻辑的 C 模板3.1 数据结构与预处理站点用一个结构体存下价格和距离排序按距离升序。排序之后先做一次去重同一距离的站只保留价格最低的那个。这一步不是为了花哨而是防止两个距离相同的站互相来回横跳导致死循环。预处理完成后把终点虚拟站点也 push 进去价格 0、距离 D再整体排一次序。#include cstdio #include algorithm #include vector using namespace std; struct Station { double price; double dist; }; bool cmp(const Station a, const Station b) { return a.dist b.dist; } int main() { double C, D, Davg; int N; scanf(%lf %lf %lf %d, C, D, Davg, N); vectorStation st; for (int i 0; i N; i) { double p, d; scanf(%lf %lf, p, d); st.push_back({p, d}); } // 终点虚拟成一个 0 元加油站 st.push_back({0.0, D}); sort(st.begin(), st.end(), cmp); // 同距离站点只保留最低价 vectorStation cleaned; for (int i 0; i (int)st.size();) { int j i; double bestP st[i].price; while (j (int)st.size() st[j].dist st[i].dist) { if (st[j].price bestP) bestP st[j].price; j; } cleaned.push_back({bestP, st[i].dist}); i j; } st cleaned; // 起点没有加油站车一升油都加不到 if (st[0].dist ! 0) { printf(The maximum travel distance 0.00\n); return 0; } ... }注意st[0].dist ! 0这个检查必须放在排序预处理之后。如果起点没有加油站就算后面有再便宜的油车也根本开不过去最大行驶距离就是 0。3.2 核心模拟循环与三种情形主循环的思路是每次站在当前站点上先扫描满油可达范围内所有站点判断落入三种情况中的哪一种再执行对应动作。我用两个标记变量记录扫描结果cheaperIdx记录范围内第一个比当前站便宜的站点下标minPriceIdx记录范围内油价最低的站点下标。扫描范围要取min(当前距离 最大满油行程, D)终点之后的站天然被排除。double maxRange C * Davg; int cur 0; double totalCost 0.0; double curFuel 0.0; while (cur (int)st.size()) { // 当前站就是终点任务完成 if (st[cur].dist D) { printf(%.2lf\n, totalCost); return 0; } double limit st[cur].dist maxRange; if (limit D) limit D; int cheaperIdx -1; int minPriceIdx -1; for (int i cur 1; i (int)st.size() st[i].dist limit; i) { if (st[i].price st[cur].price) { cheaperIdx i; break; } if (minPriceIdx -1 || st[i].price st[minPriceIdx].price || (st[i].price st[minPriceIdx].price st[i].dist st[minPriceIdx].dist)) { minPriceIdx i; } } // 情形一存在更便宜的站可能是虚拟终点 if (cheaperIdx ! -1) { double need (st[cheaperIdx].dist - st[cur].dist) / Davg; if (need curFuel) { totalCost (need - curFuel) * st[cur].price; curFuel need; } curFuel - need; cur cheaperIdx; continue; } // 情形二没有更便宜的站但有可达的真实加油站 if (minPriceIdx ! -1) { totalCost (C - curFuel) * st[cur].price; curFuel C; double consume (st[minPriceIdx].dist - st[cur].dist) / Davg; curFuel - consume; cur minPriceIdx; continue; } // 情形三范围内既没有更便宜的站也没有任何加油站 printf(The maximum travel distance %.2lf\n, st[cur].dist maxRange); return 0; }这里有几个计算细节需要仔细理解need表示从当前站开到目标站理论上需要的油量单位是升。在情形一里如果油箱里剩下的油已经足够就不买直接消耗如果不够只补差额绝不加满。情形二里C - curFuel是把油箱补满所需的油量直接按当前站价格买入然后从满油状态消耗到下一站。我在这里用consume单独算消耗是为了让代码读起来清晰。情形的判断顺序不能乱先看有没有更便宜的再看有没有任何可去的站。因为虚拟终点价格是 0只要终点在范围内cheaperIdx一定会被命中情形二和情形三天然不会误判。3.3 两个经典样例的手动推演写代码容易但真正说服自己代码是对的最好还是跑两组手算。先看一个到达不了的例子油箱 50 升每升跑 8 公里满油可跑 400 公里。总路程 1300 公里三个加油站油价元/升距离公里6.0007.003004.00800从起点站看满油范围是 400 公里只够到 300 公里那个 7 元站而且它比当前 6 元更贵范围内没有更便宜的站。规则二触发加满 50 升花 300 元开到 300 公里处油箱剩 12.5 升。此时再往前看满油范围到 700 公里800 公里那个 4 元站够不着终点更是在 1300 公里外。情形三触发最大行驶距离是 300 400 700.00 公里。再看一个能到达的例子。油箱 50 升每升跑 8 公里满油可跑 400 公里。总路程 800 公里油价元/升距离公里6.0007.003004.00600从起点出发范围内只有 300 公里的 7 元站没有更便宜的于是加满 50 升花 300 元开到 300 公里处剩 12.5 升。在 300 公里处满油范围到 700 公里600 公里处那个 4 元站比自己便宜触发规则一需要补到 37.5 升才能开到 600 公里当前手头有 12.5 升补 25 升花 25 × 7 175 元。到 600 公里处油箱刚好见底。此时终点 800 公里在 200 公里外没油不行于是补 25 升花 25 × 4 100 元。总花费 300 175 100 575.00 元。整个推演过程和代码逻辑完全吻合。3.4 复杂度与选型理由排序是 O(N log N)主循环每轮向前推进到更远的站每轮内部要线性扫描一次可达范围内的站点最坏情况下是 O(N²)。对于机试这种 N 通常在几百以内的规模完全够用。全程用 double 而不是 float是因为价格、距离、油量换算都可能产生小数float 在保留两位小数时容易出现 0.01 的累计偏差。输出的格式化统一用printf(%.2lf)不要手动做四舍五入让标准库替你做。4. 常见坑点与排查实录4.1 起点没有加油站的陷阱这是最容易白给的一个测试点。题目并没有保证第一个加油站一定在距离 0 处。如果最便宜的站在 50 公里外但你车在起点油箱是空的根本开不过去。正确输出是The maximum travel distance 0.00。我见过不少代码在排序后直接进入主循环结果因为扫描不到任何站点而输出一个错误的最大距离。排查方法很简单排序后立刻判断第一个站点的 distance 是否为 0不等于 0 就直接返回。4.2 同距离加油站的取舍与死循环风险如果两个加油站正好在同一个位置排序后它们的相对顺序是不确定的。假设你先落在价格较高的那个站扫描时发现同位置有个更便宜的need算出来是 0于是切过去到了便宜站再扫描又发现同位置那个更贵的不是更便宜但成了范围里唯一的最低价站规则二又把你拽回去。两个同距离站点就可能互相倒腾陷入死循环。我在代码里的处理是预处理阶段对同距离站点只保留最低价。这样既消除了死循环隐患也保证了逻辑上同一位置当然是选便宜的加这一直觉。4.3 浮点数精度与边界比较考察数据里经常出现恰好擦边的距离比如满油行程 400 公里下个站就在 400 公里整。用 double 做st[i].dist limit这种比较理论上应该成立但经过多轮浮点运算后误差可能会让临界值差一点点而过不了判断。稳妥的做法是在比较时加一个极小量比如st[i].dist limit 1e-8。流量大、边界多的题目里这个 epsilon 不是玄学是实打实的防御。另外最终输出保留两位小数时printf的四舍五入行为和手动round可能有细微差别统一交给printf就好。4.4 主循环死循环与推进性检查写循环类算法题最怕的就是某个分支没有让循环变量前进。我排查死循环时有一个固定的检查套路看每一个continue或下一次迭代前cur是否严格变大。在这道题里由于预处理保证了同距离站点被合并情形一和情形二都必然把cur推进到距离更远的站点所以循环一定会在有限步骤内结束。如果你发现程序在某个测试点超时优先怀疑是不是有两个同距离站在互相循环而不是去怀疑复杂度。4.5 容易忽略的虚拟终点顺序问题终点距离 D 和某个真实加油站距离相同的情况也出现过。预处理只保留最低价这一逻辑会把真实站和虚拟终点放在一起比较。由于虚拟终点价格是 0必然被保留真实站被丢弃。这个行为是对的如果终点位置本来就有加油站你到终点就结束不需要再考虑加油。5. 实操心得与扩展方向5.1 这类题在机试中的定位浙大机试喜欢出这种题意一句话、代码几十行、坑点两三个的题因为它能高效区分会背算法模板的人和真正理解贪心本质的人。这道题表面上是加油站问题实际上是个很通用的资源分配模型你在一个队列上单向移动每一步要在当前成本和未来选择面之间做权衡。类似的模型在操作系统磁盘调度、缓存淘汰策略、物流路径规划里都能找到影子。把这道题的决策框架吃透比背下二十道模板题更有价值。5.2 变种与延伸题这道题的变种非常多我在练习时整理过几个方向油箱容量无限那问题退化成全程找最便宜的站加满贪心瞬间变简单。允许回退加油状态空间瞬间变成图论得用最短路算法不再是纯贪心。油价随时间波动加上时间维度之后就变成了库存决策问题动态规划登场。百公里油耗随载重变化更贴近真实货车运输需要先建模再求解。建议刷完这道题之后顺手把 PAT 甲级里同类型的模拟贪心题放在一起对比你会发现出题人的套路高度相似先给一个生活化的场景再把约束条件藏起来最后用边界数据收割粗心的人。5.3 我最后的一点小习惯复盘这道题时我养成了一个写模拟类题目的习惯在动手写代码前先用纸笔把题意里的所有状态变量列出来。对这道题就是cur当前站点下标、curFuel当前剩余油量、totalCost累计花费、maxRange满油可行驶距离。状态变量列清楚了循环里每一步改哪个变量、加减什么量就一目了然不容易出现油量算着算着变成负数这种低级错误。另一个习惯是把虚拟节点当成一种通用手法来用。这道题把终点虚拟成 0 元加油站很多其他题目也可以这么做比如把边界条件终点可达还原成一个普通节点让统一逻辑自动覆盖它。这个思路在写 Dijsktra、区间合并、双指针类题目时都经常能派上用场。虚拟节点不只是一个技巧更是一种减少特判、让逻辑自治的编程思维方式。