1. 这道题到底在考什么1.1 从生活场景理解题目本质如果你开车跑长途油表见底之前必须找到加油站。每个加油站的油价不一样有些便宜有些贵你的油箱容量有限怎么规划加油策略才能让全程油费最低如果某些路段两个加油站之间距离太远超过满油续航那这趟行程根本走不完得直接告诉用户哪里断了。这就是 A1033 的核心贪心算法在资源补给问题上的经典应用。题目给定目的地距离、油箱容量、每单位油能跑的里程、以及沿途各加油站的油价和位置要求算出到目的地的最少花费或者判断能否到达。我第一遍做这道题的时候觉得思路很清晰——每次找最便宜的加油站加满不就行了结果提交上去一半测试点挂了。后来才发现贪心的策略远比“找最便宜的”要精细得多。这道题在 PAT 甲级里属于贪心专题的标杆题很多人卡在这里不是因为不会写代码而是因为贪心的逻辑没想透。1.2 适合谁来啃这道题如果你正在准备 PAT 甲级、蓝桥杯或者校招笔试这道题值得反复琢磨。它不像动态规划那样有固定的状态转移模板可以套贪心题的特点是思路对了代码很短思路偏了怎么调都过不了。这道题能帮你建立对贪心策略的直觉——什么时候该在当前站加满什么时候只加够跑到下一站的量什么时候干脆不加直接走。另外这道题对边界情况的考察非常细致。起点有没有加油站、终点是不是加油站、油箱容量为零、目的地距离为零……这些边界如果没考虑全测试点就会教你做人。所以它也是一道很好的“边界思维训练题”。2. 贪心策略的完整推导2.1 为什么不能简单地“找最便宜的加满”先说说我最初的错误思路。我想的是把所有加油站按油价排序从最便宜的开始能加多少加多少。但这个思路有个致命问题——你到了加油站才能加油不能跳过近处的站去远处的便宜站。油是消耗品你得保证在到达下一个加油站之前油够用。还有人会想那我在每个加油站都看看如果下一个站比我便宜我就只加够到下一个站的油如果下一个站比我贵我就在当前站加满。这个思路方向是对的但不够完整。因为“下一个站”可能很远你只加够到下一个站的油万一到了之后发现那个站更贵你被迫加高价油反而亏了。正确的贪心策略需要看得更远在当前加油站往前看所有满油能到达的加油站找到第一个油价低于当前站的站。如果找到了就只加够跑到那个站的油如果找不到说明当前站是满油范围内最便宜的那就加满然后跑到范围内油价最低的那个站。2.2 贪心选择的严格证明为什么这个策略是最优的我用反证法来说。假设当前在站 A满油能到达的范围内第一个比 A 便宜的站是 B。如果我们不在 A 只加到 B 的量而是加满了那么多出来的油会在 B 之后被消耗。但 B 的油价比 A 便宜在 B 加油比在 A 加油更划算所以在 A 多加的油是浪费。因此只加到 B 的量是最优的。如果 A 的满油范围内没有比 A 更便宜的站说明 A 是这段范围内最便宜的。那当然应该在 A 加满因为后面无论到哪个站油价都不会比 A 低。加满之后选择范围内油价最低的站作为下一站这样能最大化利用 A 的低价油。这个证明的关键在于油价是全局可比较的而油箱容量限制了你的“视野”。贪心策略本质上是在每个决策点利用当前能掌握的全部信息做出局部最优选择而这个局部最优恰好能导出全局最优。2.3 关键变量的设计在写代码之前先把变量想清楚。我用的是 C但思路对任何语言都通用。C_max油箱容量单位是升D目的地距离单位是公里D_avg每升油能跑的公里数N加油站数量每个加油站有price每升油价和distance离起点的距离满油续航 C_max * D_avg这个值决定了从当前站最远能到哪。还有一个容易忽略的点起点的处理。如果起点没有加油站而目的地距离大于零那直接输出无法到达。因为你的车初始没油走不了。这个边界我第一次做的时候就漏了测试点直接报错。另外终点可能也有加油站。如果终点有加油站它的油价其实不重要因为你到了就结束了不需要再加。但它的位置信息要参与排序和遍历。3. 代码实现与逐行拆解3.1 数据结构与输入处理#include cstdio #include algorithm using namespace std; struct Station { double price; double distance; }; bool cmp(Station a, Station b) { return a.distance b.distance; } Station stations[510]; int main() { double C_max, D, D_avg; int N; scanf(%lf %lf %lf %d, C_max, D, D_avg, N); for (int i 0; i N; i) { scanf(%lf %lf, stations[i].price, stations[i].distance); } // 把目的地也当作一个加油站油价设为0其实用不到 stations[N].price 0; stations[N].distance D; N; sort(stations, stations N, cmp); // 起点没有加油站直接走不了 if (stations[0].distance ! 0) { printf(The maximum travel distance 0.00\n); return 0; } // 后续逻辑... }这里有个细节我把目的地也加入加油站数组油价设为 0。这样做的好处是遍历的时候不用单独处理终点统一逻辑。但要注意终点的油价 0 不能参与“找更便宜的站”的比较否则会出问题。实际处理时如果当前站就是终点直接结束。排序是必须的因为输入不保证按距离有序。PAT 的测试数据经常故意打乱顺序不排序直接遍历会得到错误结果。3.2 核心贪心循环double now_price stations[0].price; double now_pos 0; double now_gas 0; // 当前油箱里的油量 double total_cost 0; double max_reach C_max * D_avg; int i 0; // 当前所在加油站的下标 while (i N - 1) { // 不是最后一个终点 // 找满油范围内第一个比当前站便宜的站 int cheaper -1; int cheapest -1; double cheapest_price 1e9; for (int j i 1; j N stations[j].distance - stations[i].distance max_reach; j) { if (stations[j].price stations[i].price) { cheaper j; break; } if (stations[j].price cheapest_price) { cheapest_price stations[j].price; cheapest j; } } if (cheaper ! -1) { // 找到了更便宜的站只加够跑到那里的油 double need (stations[cheaper].distance - stations[i].distance) / D_avg; if (now_gas need) { total_cost (need - now_gas) * stations[i].price; now_gas need; } now_gas - (stations[cheaper].distance - stations[i].distance) / D_avg; i cheaper; } else if (cheapest ! -1) { // 没找到更便宜的加满跑到范围内最便宜的站 total_cost (C_max - now_gas) * stations[i].price; now_gas C_max; now_gas - (stations[cheapest].distance - stations[i].distance) / D_avg; i cheapest; } else { // 满油也到不了任何站 double reach stations[i].distance max_reach; printf(The maximum travel distance %.2f\n, reach); return 0; } } printf(%.2f\n, total_cost);这段代码有几个容易出错的地方我逐个说。第一now_gas的更新逻辑。每次移动之后要减去路上消耗的油。这个减法要在加油之后做顺序不能反。我见过有人先减再加油结果油量算错。第二cheaper和cheapest的查找范围。循环条件是stations[j].distance - stations[i].distance max_reach注意是小于等于不是小于。刚好等于满油续航的情况也要算进去。第三终点的处理。当i到达N-1也就是终点时循环结束直接输出总花费。不需要在终点加油。第四浮点数比较。油价和距离都是浮点数直接用比较没问题但要注意精度。PAT 的测试数据一般不会卡精度但保险起见可以用1e-8作为容差。3.3 一个完整的执行示例假设输入是50 1300 12 8 6.00 1250 7.00 600 7.00 150 7.10 0 7.20 200 7.50 400 7.30 1000 6.85 300排序后的加油站顺序是下标距离油价007.1011507.0022007.2033006.8544007.5056007.00610007.30712506.00813000终点满油续航 50 * 12 600 公里。从站 0距离 0油价 7.10出发满油能到距离 600 以内的站。范围内第一个比 7.10 便宜的是站 1油价 7.00距离 150。所以只加够跑到站 1 的油150 / 12 12.5 升花费 12.5 * 7.10 88.75。到站 1 后油箱空了。范围内第一个比 7.00 便宜的是站 3油价 6.85距离 300。加够跑到站 3 的油(300-150)/12 12.5 升花费 12.5 * 7.00 87.50。到站 3 后油箱空了。范围内距离 300 到 900的站有站 44007.50、站 56007.00、站 61000 超出范围。没有比 6.85 更便宜的。所以加满花费 50 * 6.85 342.50。然后跑到范围内最便宜的站 5油价 7.00距离 600。到站 5 后消耗了 (600-300)/12 25 升剩余 25 升。范围内距离 600 到 1200的站有站 610007.30。没有比 7.00 更便宜的。加满需要 25 升花费 25 * 7.00 175.00。跑到站 6。到站 6 后消耗了 (1000-600)/12 33.33 升剩余 50 - 33.33 16.67 升。范围内距离 1000 到 1600的站有站 712506.00、站 81300终点。站 7 比 7.30 便宜所以只加够跑到站 7 的油(1250-1000)/12 20.83 升。当前有 16.67 升还需要加 4.17 升花费 4.17 * 7.30 30.42。到站 7 后消耗了 20.83 升油箱空了。站 7 油价 6.00范围内有终点1300。终点油价是 0比 6.00 便宜所以只加够跑到终点的油(1300-1250)/12 4.17 升花费 4.17 * 6.00 25.00。总花费 88.75 87.50 342.50 175.00 30.42 25.00 749.17。这个结果和标准答案一致。你可以用这个例子来验证自己的代码。4. 那些年我踩过的坑4.1 边界情况清单这道题的边界情况特别多我整理了一个清单每次写完代码都对照检查一遍边界情况处理方式容易犯的错起点没有加油站直接输出最大距离 0.00忘记判断导致数组越界或死循环目的地距离为 0直接输出 0.00没考虑代码可能进入循环油箱容量为 0如果目的地距离大于 0输出 0.00没考虑除零或逻辑错误终点有加油站终点油价不参与比较把终点油价当成正常站贪心策略出错满油刚好到下一站算作可达用了严格小于漏掉这种情况多个加油站同一位置按油价排序取最低的没去重逻辑混乱满油到不了任何站输出当前距离 满油续航忘记加当前距离只输出了续航4.2 浮点数精度问题PAT 的测试数据里距离和油价都是浮点数。浮点数比较和运算会引入误差处理不好会导致答案偏差。我的经验是能用整数就不用浮点数。比如距离可以乘以 100 变成整数油价可以乘以 100 变成整数分。但这样代码会复杂一些。如果直接用浮点数注意以下几点比较两个浮点数是否相等时用fabs(a - b) 1e-8输出时用%.2fPAT 一般接受 0.01 以内的误差累加花费时尽量用double不要用floatfloat精度不够我遇到过一种情况某个测试点的答案和我的输出差了 0.01就是因为浮点数累加误差。后来我把所有中间结果都保留更多小数位最后再四舍五入就过了。4.3 贪心策略的常见误区误区一只看下一个站。前面说过只看下一个站不够因为下一个站可能很远你只加够到那里的油到了之后发现油价很贵被迫加高价油。正确的做法是看满油范围内所有站。误区二找范围内最便宜的站然后加满。这个策略在大多数情况下是对的但如果范围内有比当前站更便宜的站你应该只加到那个站的油而不是加满。因为那个站更便宜在那里加油更划算。误区三在当前站加满然后跑到范围内最便宜的站。这个策略在“范围内没有更便宜的站”时是对的但如果范围内有更便宜的站你就应该直接跑到那个站而不是跑到最便宜的站。因为“第一个更便宜的站”可能不是“最便宜的站”但它是你能够到达的、比当前站便宜的站中最近的一个跑到它那里加油是最优的。这三个误区我全踩过每次都是提交后看到“答案错误”才回头改。后来我总结了一句话贪心策略的核心是“在当前能看到的范围内做出最有利的决策”而不是“做出全局最有利的决策”。因为你看不到全局只能看到满油续航范围内的站。5. 从这道题延伸出去的思考5.1 贪心算法的适用条件这道题能用的贪心策略依赖于两个条件最优子结构和贪心选择性质。最优子结构是说问题的最优解包含子问题的最优解。在这道题里如果你从站 A 到站 B 的加油策略是最优的那么从站 B 到终点的加油策略也应该是最优的。这个性质保证了你可以一步一步地做决策而不需要回头修改之前的决策。贪心选择性质是说每一步的局部最优选择能导致全局最优。在这道题里就是“在当前站做出最有利的加油决策”能导致“全程花费最少”。这个性质不是所有问题都有的比如背包问题就不能用贪心因为选择单位价值最高的物品不一定能得到最优解。判断一道题能不能用贪心我的经验是如果每一步的决策只依赖于当前状态和未来的有限信息而且这个决策不会因为未来的选择而变得不利那就可以尝试贪心。如果决策之间相互影响比如选了 A 就不能选 B那可能需要动态规划。5.2 类似题目的解题套路PAT 里还有几道和这道题思路类似的贪心题比如“月饼”A1070、“组个最小数”A1023等。它们的共同特点是有一个明确的贪心策略而且这个策略可以用“交换论证”来证明。交换论证是说假设存在一个最优解它的第一步选择和贪心策略不同你可以通过交换操作把它变成贪心策略的选择而且不会让解变差。如果能做到这一点就证明了贪心策略的正确性。这道题的交换论证是这样的假设最优解在站 A 没有选择“第一个更便宜的站”而是选择了别的站。你可以把在别的站加的油换成在“第一个更便宜的站”加因为那个站更便宜所以花费不会增加。通过一系列这样的交换最优解可以变成贪心解。5.3 实际工程中的资源补给问题这道题虽然是一道算法题但它背后的资源补给问题在现实中很常见。比如物流配送中货车需要在沿途的加油站加油每个加油站的油价不同怎么规划加油策略最省钱比如无人机配送中无人机需要在沿途的充电站充电每个充电站的电价不同怎么规划充电策略最省电这些问题的核心和这道题是一样的在资源有限、补给点离散、补给成本不同的情况下如何规划补给策略。解决思路也类似在每个补给点根据当前资源和未来补给点的信息做出最优决策。当然现实问题比算法题复杂得多。比如油价可能会波动路况可能会影响油耗补给点可能会排队。但基本的贪心思路是一样的在当前能掌握的范围内做出最有利的决策。6. 调试与验证的实用技巧6.1 用对拍验证贪心策略贪心题最怕的就是策略错了但自己不知道。我常用的验证方法是对拍写一个暴力搜索的版本随机生成小规模测试数据比较两个版本的输出。暴力搜索的思路是对于每个加油站枚举加多少油可以离散化比如每次加 1 升然后递归搜索所有可能的加油方案取最小花费。小规模数据下暴力搜索是可行的。对拍的代码框架大概是这样的// 随机生成测试数据 void generate() { // 随机生成 C_max, D, D_avg, N // 随机生成每个加油站的 price 和 distance } // 运行贪心版本 double greedy() { ... } // 运行暴力版本 double brute_force() { ... } int main() { for (int t 0; t 1000; t) { generate(); double g greedy(); double b brute_force(); if (fabs(g - b) 1e-6) { printf(Mismatch: greedy%.2f, brute%.2f\n, g, b); // 输出测试数据 break; } } }我用这个方法发现了自己代码里的好几个 bug包括边界情况处理不当、浮点数精度问题等。对拍虽然花时间但比盲目提交然后看“答案错误”要高效得多。6.2 手工模拟小案例除了对拍手工模拟小案例也很重要。我一般会构造几个简单的测试数据手动算一遍答案然后和代码输出对比。比如// 案例1起点没有加油站 50 100 12 1 7.00 50 // 答案The maximum travel distance 0.00 // 案例2满油到不了任何站 50 100 12 1 7.00 0 // 答案The maximum travel distance 600.00 // 案例3终点有加油站 50 100 12 2 7.00 0 6.00 100 // 答案100 / 12 * 7.00 58.33这些案例覆盖了主要的边界情况每次改完代码都跑一遍能快速发现回归问题。6.3 常见错误代码模式我整理了几个常见的错误代码模式如果你写出来的代码长这样大概率有问题模式一在循环里修改循环变量。比如在for循环里修改i的值导致循环行为不可预测。贪心题的循环通常用while因为i的跳转不是线性的。模式二忘记更新油箱油量。每次移动之后一定要减去路上消耗的油。我见过有人只更新位置不更新油量结果油量越算越多。模式三在终点站加油。到达终点就结束了不需要加油。如果代码在终点站还执行加油逻辑花费会算多。模式四满油续航计算错误。满油续航 C_max * D_avg不是C_max / D_avg。这个错误很低级但我在紧张的时候犯过。模式五距离差计算错误。两个站之间的距离是stations[j].distance - stations[i].distance不是stations[j].distance。这个错误在排序后不容易发现因为下标和距离可能恰好对应。7. 性能优化与代码风格7.1 时间复杂度分析这道题的时间复杂度是 O(N^2)因为对于每个加油站都要遍历满油范围内的所有站。N 最大是 500N^2 250000完全在可接受范围内。如果想优化到 O(N log N)可以用单调栈预处理每个站右边第一个比它便宜的站。但 PAT 的数据规模不大没必要过度优化。我建议先把 O(N^2) 的版本写对再考虑优化。7.2 代码可读性建议贪心题的代码容易写得一团糟因为逻辑分支多。我的建议是把“找第一个更便宜的站”和“找范围内最便宜的站”封装成函数主循环只负责决策用有意义的变量名比如first_cheaper而不是fccheapest_station而不是cs在每个分支加注释说明这个分支的贪心逻辑把边界情况的判断放在最前面避免嵌套太深// 找满油范围内第一个比当前站便宜的站 int findFirstCheaper(int cur, double maxReach) { for (int j cur 1; j N stations[j].distance - stations[cur].distance maxReach; j) { if (stations[j].price stations[cur].price) { return j; } } return -1; } // 找满油范围内油价最低的站 int findCheapest(int cur, double maxReach) { int cheapest -1; double minPrice 1e9; for (int j cur 1; j N stations[j].distance - stations[cur].distance maxReach; j) { if (stations[j].price minPrice) { minPrice stations[j].price; cheapest j; } } return cheapest; }这样主循环就清晰多了while (i N - 1) { int cheaper findFirstCheaper(i, maxReach); if (cheaper ! -1) { // 只加够跑到 cheaper 的油 ... } else { int cheapest findCheapest(i, maxReach); if (cheapest ! -1) { // 加满跑到 cheapest ... } else { // 到不了任何站 ... } } }7.3 测试用例设计除了 PAT 官方的测试数据我建议自己设计几组测试数据覆盖以下场景只有一个加油站且在起点只有一个加油站但不在起点多个加油站油价递增多个加油站油价递减多个加油站油价先增后减满油续航刚好等于两个站之间的距离满油续航刚好小于两个站之间的距离这些测试数据能帮你发现大部分逻辑错误。我一般会把它们写在一个单独的测试文件里每次改完代码都跑一遍。8. 从解题到教学的思维转变8.1 如何向别人讲清楚这道题如果你要给别人讲这道题我建议按这个顺序先讲生活场景——开车加油让听的人理解问题背景。然后讲暴力思路——枚举所有可能的加油方案但复杂度太高。接着讲贪心思路——在每个站做出局部最优决策。最后讲正确性证明——用交换论证说明贪心策略为什么是对的。讲的时候要注意不要一上来就讲代码。代码是最后的实现思路才是核心。我见过很多人讲题的时候直接贴代码听的人一头雾水。正确的做法是先讲思路再讲代码最后讲边界情况。8.2 贪心思维的训练方法贪心思维不是天生的需要刻意训练。我的训练方法是第一步多做经典贪心题。比如区间调度、霍夫曼编码、最小生成树等。这些题的贪心策略比较典型做多了能形成直觉。第二步每道题都尝试证明。不要满足于“代码过了”要问自己“为什么这个策略是对的”。用交换论证或者反证法证明一遍能加深理解。第三步尝试找反例。对于自己想的贪心策略尝试构造反例。如果找不到反例说明策略可能是对的如果找到了说明策略有问题。第四步总结套路。贪心题虽然变化多但有一些常见套路比如“按结束时间排序”、“每次选最小的”、“维护一个优先队列”等。总结多了遇到新题就能快速识别。8.3 这道题对面试的价值这道题在面试中出现的频率不高因为它的场景比较特定。但它的贪心思维在面试中很常见。面试官可能会问“如果你要设计一个加油规划系统你会怎么做”这时候你就可以把这道题的思路讲出来。面试的时候面试官更看重你的思考过程而不是最终答案。你可以先说暴力思路然后说优化思路最后说边界情况。即使代码没写完只要思路清晰面试官也会认可。另外这道题的边界情况处理也能体现你的工程思维。面试官可能会问“如果起点没有加油站怎么办”“如果终点有加油站怎么办”这些问题考察的是你对细节的关注程度。9. 个人实操心得这道题我前前后后做了三遍。第一遍看题解似懂非懂第二遍自己写卡在边界情况第三遍重新推导贪心策略才真正理解。最大的心得是贪心题不要急着写代码先把策略想清楚用几个小例子验证一遍再动手。我第一遍做的时候看完题就开始写结果写了 100 多行逻辑一团糟调了半天也过不了。后来我把策略写在纸上用几个例子手动模拟了一遍发现了好几个逻辑漏洞改完之后代码只有 60 多行一次就过了。另一个心得是边界情况要单独测试。PAT 的测试数据里边界情况的测试点往往占很大比例。如果你只测试常规情况很可能挂掉一半测试点。我建议把边界情况列一个清单每写完一个功能就对照检查一遍。最后说一个调试技巧在代码里加输出语句打印每一步的决策。比如打印“当前在站 X油价 Y油箱 Z 升选择站 W”。这样运行的时候能看到完整的决策过程哪里出错一目了然。调通之后再把输出语句删掉。这道题虽然只是一道算法题但它背后的贪心思维和边界处理能力在实际工程中同样重要。无论是做资源调度、路径规划还是成本优化都需要这种“在有限信息下做出最优决策”的能力。希望这篇分享能帮你少走一些弯路顺利拿下这道题。