1. 一道1999年的NOIP老题凭什么到现在还挂在GESP练习单上在洛谷上搜P1016你会看到题目名字叫“旅行家的预算”来源是NOIP 1999提高组。单论年龄它比现在绝大多数备赛GESP的学生年龄都大。可奇怪的是在很多GESP四、五、六级甚至七级的学习路线清单里这道题都会被反复拎出来。原因很简单它把“读题建模、贪心决策、边界判断、浮点输出”四件事压缩到了一个不超过100行的程序里而这四件事恰好是GESP从四级开始往后每一级都在考察的方向。很多人第一眼看到这道题会以为它是个模拟题一辆车从A到B路上有加油站油箱容量有限求最少花钱。模拟一下每个加油站应该加多少油不就行了真写起来就会发现问题没那么简单——你当前油量不是整数下一站不是只有一个油价又各不相同加多加少直接影响后续所有决策。所以它实际上是“带约束的最优化问题”考察的是贪心策略。从GESP的分级来说四级开始明确要求“能够理解贪心算法的基本思想并解决简单的贪心问题”五级要求“能对贪心策略的正确性进行解释说明”六级及以上则需要在复杂约束下构造正确的贪心模型。P1016恰好横跨了这三个层次。四级的孩子可以把这道题当作“高级模拟”来练哪怕证明不完整五级的孩子必须能说清楚“为什么油箱里还有油时也可能需要继续加油”六级的孩子则应该能自己推出那两个关键分支。做这道题之前比较合理的前置训练线是能熟练使用结构体排序能处理双精度浮点数输出能看懂“无解”型题目的输出约定。如果这三样都还不太稳建议先去做一两道排序和简单模拟的题再回来否则容易把时间浪费在调试语法而不是思考策略上。还有一点值得说这道题的题面很长但信息密度不低。我见过不少学生一看到“计算结果是四舍五入至小数点后两位”就开始慌其实它只是提醒你用固定两位小数输出不存在什么高精度要求。真正容易丢分的反而是那些藏在题干角落里的条件比如“出发时油箱是空的”“油站N可以为零”这类话。2. 题目参数与最优路径到底要算什么2.1 五个输入量和一个清零的油箱题目会给五个量两地距离D1油箱最大容量C每升油能跑的公里数D2出发点的油价P沿途加油站数量N。接着给N行每行两个数该油站离出发点的距离以及该站的每升油价。这里最关键的一句话是“假设出发时油箱是空的”。这意味着你在起点必须至少先买一点油才能走。而且买油只能按“升”思考不是按“钱”思考——你先看需要多少升再决定在哪个站买。需要注意N可以为0。也就是说路上可能一个加油站都没有。这时候别慌直接从起点开车到终点能到就只买“全程耗油量”对应的油不能到就输出No Solution。2.2 样例手算为什么不是“见站就加”洛谷原题的样例是这样的275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2一辆车两地相距275.6公里油箱11.9升每升跑27.4公里起点油价2.8元两个加油站分别距起点102公里和220公里。先算一箱油最多能跑多远11.9 × 27.4 326.06公里比全程长。所以理论上如果起点油价是全程最低加满一箱直接怼到终点都行。但实际情况是220公里处的油价比起点便宜2.2 2.8所以正确的省钱思路是利用220公里处的低价油跑最后一段而不是在起点的2.8元油价上多买。从起点到第二个加油站距离220公里需要的油量是220 ÷ 27.4 ≈ 8.03升。从起点只买这8.03升花 8.03 × 2.8 ≈ 22.48元。到了220公里处油箱里油量已经归零忽略浮点误差。从这个站到终点还剩55.6公里需要 55.6 ÷ 27.4 ≈ 2.03升花 2.03 × 2.2 ≈ 4.47元。合计约 26.95元。第一个加油站设在102公里处油价2.9比起点还贵。最优路线里完全可以不停它哪怕路过也当它不存在。这就是这道题的第一层思考加油站不是“经过就必须消费”而是“只有符合省钱条件才消费”。2.3 把终点当成一个0元虚拟加油站写代码时很多同学的习惯是“循环模拟到最后一个站再单独处理终点”。这个思路没错但会多出一整段特判代码还容易漏。更干净的做法是把终点视为一个虚拟加油站距离设为D1油价设为0。为什么油价设为0因为到达终点之后你不需要再买任何油。而在贪心算法里“价格最低”天然意味着“我一定要尽量少在这个站之前花钱”。把终点油价设为0之后前面所有的“找更便宜的站”逻辑能自动在终点处收口只要终点在当前油量能到达的范围内算法就会选择只加“刚好够到终点”的油量而不是提前加满。这个技巧非常实用在很多最短路和区间覆盖题目里都能用。凡是遇到“最后一个点不是加油站但需要单独处理”的情况加一个虚拟目标点往往能让逻辑统一也减少边界bug。3. 贪心策略的完整推导三种局面对应三个决策3.1 为什么这道题适合贪心而不是动态规划看到“最小费用”四个字很多人第一反应是动态规划。但仔细分析就会发现这个问题的状态非常连续油量是实数不是整数加油站的选择也只受到“能不能到达”的约束而不受之前选择路径的影响。也就是说在当前站点做决策时后续的费用只取决于“我从这里带了多少油出发”“后面油价分布如何”跟之前是怎么到这里的无关。这就是无后效性。更关键的是油价是一个一维序列你只能从左往右开。这么强的线性结构下贪心几乎总是优于DP既节省时间又容易证明。动态规划需要把油量离散化成格点反而引入了大量状态和精度问题属于自己给自己找麻烦。3.2 决策A可达范围内存在比本站更便宜的油站假设我在当前站点油箱加满后能覆盖到后面若干站。如果在这些站里存在一个站的价格比我当前站便宜那我应该怎么买答案不是“买到那个站”而是“一滴不多加只买刚好能开到那个站的油量”。理由很直观既然前面的站更便宜我在当前这个高价站每多买一升就多亏一升的差价。最好的做法就是让低价油站尽可能多承担后续路程的油耗当前高价站的油只用来“够到”低价站即可。还有个细节当“更便宜的站”不止一个时应该选哪一个标准实现里选的是“第一个价格低于当前油价的站”也就是从当前站往后扫描时第一次遇到比本站便宜的站而不是“范围内最便宜的那个”。有人会问如果后面有个特别便宜的站我应该直接跳过这个“第一个便宜站”吗不用。因为即使到了第一个便宜站如果它并不是全局最低算法在那站会继续执行同样的判断找到下一个更便宜的站再只加“刚好够到下一站”的油。这样最终效果是完全等价的而且每次只向前推进一小步程序逻辑更简单。3.3 决策B可达范围内所有油站都比本站贵如果没有一个加油站比当前站便宜那当前站点就是后面这一段里油价最低的。这时候策略完全反过来把油箱加满。为什么会加满而不是只加到够去最便宜的那一站因为以后每一滴油都比现在贵。你在这个站能带走的每一升油都会替代未来某个高价站的油。油箱容量就那么多加的越多节省越多所以必须顶格加满。但加满之后开向哪儿答案是“可达范围内油价最低的那个站”。因为你已经加满了油是满的下一个决策点放在哪里能最大程度降低未来成本当然是最便宜的那个站点。到了那里再重复同样的贪心判断。3.4 无解判断要放在最前面如果当前站点加满油后连下一站都到不了那就是彻底的无解直接输出No Solution。这句话听起来很简单但实际实现中有一半以上的人会在这个环节出错。因为你不能只看“起点到终点能不能一箱油跑完”还要看“每一段相邻加油站之间的距离有没有超过一箱油续航”。只要有一段超过无论怎么规划最终都会在中间抛锚因此必然无解。这个无解检查必须放在主循环之前统一做而不是在循环里发现到不了时才临时输出。统一检查的另一个好处是它可以保证主循环里“当前站点加满后至少能到下一站”这个前提永远成立贪心分支不需要再对“范围为空”做额外处理。4. 完整C实现结构体、排序与主循环4.1 数据建模起点和终点都放进结构体我习惯这样定义#include bits/stdc.h using namespace std; struct Node { double dis; // 离起点的距离 double pri; // 油价 }; int main() { double D1, C, D2, P; int N; cin D1 C D2 P N; vectorNode a; a.push_back({0.0, P}); // 起点距离0油价P for (int i 0; i N; i) { double d, p; cin d p; a.push_back({d, p}); } a.push_back({D1, 0.0}); // 终点距离D1油价0 sort(a.begin(), a.end(), [](const Node x, const Node y) { return x.dis y.dis; });把起点也放进结构体是为了让循环逻辑从“当前位置”出发不需要为起点单独写一份处理代码。把终点当成0元加油站后主循环里最后一站的处理和普通站完全一致。排序在这里是必须的尽管大部分测试数据已经是升序输入但你不能依赖这个约定。4.2 无解预检double maxRun C * D2; for (int i 0; i (int)a.size() - 1; i) { if (a[i 1].dis - a[i].dis maxRun) { cout No Solution endl; return 0; } }这个for循环检查的是“任意相邻两站之间的距离是否超过一箱油续航”。注意排序之后才是相邻所以排序这一步必须放在检查前面。一旦出现某一段距离超标说明无论怎么规划车辆都会在这一段中间耗尽油量直接无解。4.3 主循环与三种决策double oil 0.0; // 当前油量 double ans 0.0; // 总花费 int i 0; // 当前所在加油站的下标 while (i (int)a.size() - 1) { int cheaper -1; // 第一个比当前油价更便宜的站 int minPos -1; // 可达范围内油价最低的站 for (int j i 1; j (int)a.size(); j) { if (a[j].dis - a[i].dis maxRun) break; if (minPos -1 || a[j].pri a[minPos].pri) { minPos j; } if (cheaper -1 a[j].pri a[i].pri) { cheaper j; } } if (cheaper ! -1) { // 决策A只加刚好能到 cheaper 站的油 double need (a[cheaper].dis - a[i].dis) / D2; if (need - oil 1e-9) { ans (need - oil) * a[i].pri; oil need; } oil - need; i cheaper; } else { // 决策B本站加满然后去范围内最便宜的站 ans (C - oil) * a[i].pri; oil C; double need (a[minPos].dis - a[i].dis) / D2; oil - need; i minPos; } } printf(%.2f\n, ans); return 0; }这段代码的主循环终止条件是i到达终点虚拟站。由于终点油价是0从任意非终点站出发终点一定是“更便宜站点”的候选所以算法不会在错误的时间进入决策B。只有当终点不在当前油量加满后的可达范围内时才会真的执行“加满并去范围最低站点”的分支。4.4 复杂度够不够用这个程序最外层循环是O(N)个决策点每个决策点内部会扫描后面所有站点因此最坏复杂度是O(N²)。原题N最多100O(N²)绰绰有余。GESP的代码提交环境中这样的复杂度也完全能过。即使N放大到1000O(N²)也就是百万级运算依然没问题。如果非要进一步优化可以在排序后用一个单调栈或双指针维护“下一个更低价格的位置”把复杂度降到O(N log N)但对这道题来说属于过度设计。竞赛里“能过就是好代码”不需要追求理论上的极致。5. “No Solution”判定顺序与浮点数精度陷阱5.1 先排序再检查相邻站距离无解检查的前提是“相邻”。如果输入数据没有按距离排好序直接检查输入顺序里的相邻站结果一定是错的。虽然题目通常保证加油站按距离递增给出但你不能赌。尤其是自己造数据测试的时候一定要先排序。这个看似无关紧要的小步骤能避免一堆莫名其妙的问题。还有一个小细节排序后如果出现距离相同的站点处理时要有心理准备。虽然原题几乎不会这样出但如果你自己扩展练习重复距离会让“相邻站距离为0”预检不会报错但主循环里需要判断是哪个站更便宜。我一般遇到这种情况会在排序比较器里额外规定距离相同时油价低的排前面。这样即使数据里有重复位置贪心逻辑也能自动选择更优价格。5.2 N0的情况当N0时输入里不会出现任何加油站。处理起来很简单先是起点和终点两个点放进结构体排序后两个点相邻。如果D1 C × D2无解否则从起点只买D1/D2升油费用是D1/D2 × P。用上文代码跑N0也完全没问题a里只有起点和终点两个元素预检检查两点距离是否超过maxRun主循环里从起点出发终点价格0一定小于起点价格P于是进入决策A加刚好够到终点的油。所以不需要单独写特判。5.3 double比较和输出格式这题所有数字都用double来存不要用float否则可能在边界距离上翻车。比较两个浮点数大小尽量不要写成x y这种直接判断而是用x - y 1e-9之类的容差比较。输出时用printf(%.2f\n, ans)或者cout fixed setprecision(2) ans endl;注意要保留两位小数。这里的四舍五入并不是要求你手写标准格式化输出会自动处理。有个细节值得提醒题目描述里写的“计算结果四舍五入至小数点后两位”在实际评测中就是要求精确输出两位小数。不要自己额外做任何“四舍五入”操作避免二次舍入误差。5.4 一个容易忽略的浮点场景当油量计算出现“刚好够到下一站”的情况时浮点误差可能让程序认为差一点点于是多买了0.0000001升油。这通常不会影响最终答案的两位小数输出但如果某个测试点数据恰好卡在边界上可能就会出现微小偏差。稳妥的做法是在判断if (oil need)时改为if (need - oil 1e-9)这样既保留真实比较语义又避免了浮点噪声带来的误判。代码里其他浮点比较也建议统一加上这个容差。5.5 实践中的自测数据写完代码后我一般会准备几组自测数据// 例1起点加满10L到50公里处油价4元的加油站再加5L到终点 // 输入 100 10 10 5 1 50 4 // 输出应该是70.00 // 例2一箱油根本撑不到下一个站 // 输入 100 10 5 5 1 60 4 // 10*550 60输出 No Solution // 例3全程不需要加油 // 输入 50 10 10 5 0 // 输出 25.00 // 例4中间全是贵的油起点加满直接跑 // 输入 100 10 10 5 1 10 100 // 起点加满10L花50终到答案50.00例4很多人会写错因为10公里处有个天价加油站但到终点需要10升油一箱油正好够所以完全不用理它。正确输出是50.00而不是“在起点只加10公里的油然后去天价站”。6. 从NOIP到GESP一道题拆出四级、五级、六级三种考法6.1 四级视角把贪心当高级模拟来练GESP四级的大纲里“贪心”并不是一个特别深的考点更多是让你接触“每一步都做当前最优选择”这个思想。P1016恰好能承担这个角色。如果孩子只学到四级我建议先不要给他们讲“决策A/B的完整证明”而是让他们先看懂代码流程先检查能不能到再在每个站找后面有没有更便宜的站。有就少加没有就加满。这个口诀足够他们把这个题调通。调通之后可以做几道类似结构的题做迁移训练比如简单的区间选点、部分背包。它们都在强调同一个道理局部最优能推出全局最优的条件是什么。四级的孩子能意识到这一点就已经超过很多“只会写模板”的同龄选手了。6.2 五级视角必须能解释“为什么这么做是对的”到了GESP五级单纯能AC是不够的评委会看你能不能把策略讲清楚。这时候需要做一些更扎实的证明训练。反证法是最好用的证明方式。比如决策A如果在当前高价站多买了油而后面有低价站那么这多买的油本来可以在低价站买因此当前方案一定不是最优所以“只买刚好够到低价站”才是最优。决策B的证明思路类似后面所有站都更贵在当前站少买了一升未来就得在更贵的站补一升总费用只会增加所以必须加满。这个“反证交换论证”的思维是五级和四级在同一个题目上的关键分水岭。写题解、画图、给同学讲题都是不错的训练方式。如果只是闷头刷题很难真正过渡到“会证明”的层次。6.3 六级以上视角把单点决策抽象成普适模型到六级以后题目不会只考课本原题而会换皮。比如把“油箱容量”改成“电池容量”把“油价”改成“充电价格”甚至把“单程”改成“可以回头”你就需要重新设计贪心决策。P1016真正的价值在于它提供了一个非常好的“多约束贪心”模板在某个可决策节点上如何利用范围枚举选择下一步目标。这个模板在后续的很多题里都能复现比如带往返运输的最小费用、带容量限制的区间覆盖、甚至某些资源调度问题。六级及以上的备赛不应该满足于背题解而是要尝试自己改题。我带的不少学生会在做完P1016之后自己加一两个限制条件再问自己怎么做。这种训练对GESP七、八级以及后续冲击更高赛事的帮助往往比多刷十道类似题更有效。6.4 推荐练习顺序如果要从零开始挑战这道题我给一条比较顺的路线先用30分钟自己思考画出能到达的站点范围图。看一遍标准代码的框架不急着看全先把“无解检查”和“主循环”的边界搞清楚。自己敲一遍跑通样例。把样例手算一遍确认结果对得上。自己构造3-4个边界测试点尤其是“N0”“一箱油刚好到”“中间有很贵的站”这几类。尝试不看代码用文字把贪心策略写出来。这套流程走完这道题才算真正吃透。7. 写完之后我沉淀下的几条实操体会第一这道题最容易被低估的地方是“读题”。很多学生第一遍看完题面以为只需要在“最便宜的加油站加满油”就够了样例都能过但一提交就只能拿到部分分。真正把“每个站点的油量状态”当作连续量来理解和建模才是这道题的核心门槛。第二代码里不要写“看起来很聪明”的优化。比如有人会在主循环里反复做浮点运算优化或把油价做一大堆常数处理。这些在这个数据范围下都毫无意义反而容易引入精度错误。保持简单、直接、容差到位是我在这道题上最推荐的写法。第三如果调试时发现输出只差0.01先别急着怀疑算法先检查是不是格式化输出写错了或者某一处直接用比较了浮点数。我见过太多因为这两点被卡半小时的情况。第四这道题对一个备赛者最宝贵的训练不是“学会了贪心”而是“建立起了从题面提取约束条件、抽象成数学模型、写代码、造数据验证”的完整闭环。GESP从四级到六级每一级都在反复强化这条链路。把这套方法论练稳了比多刷十道题更管用。我个人的习惯是每带一批学生刷P1016都会要求他们提交完AC后再写一段不超过200字的“解题说明”强迫自己把决策A和决策B的逻辑用大白话讲清楚。这个习惯后来帮他们在GESP五级、六级里解决了很多需要“解释设计思路”的题型。如果你也是自己备考而不是跟班学建议同样试试这个办法AC之后合上代码用两段话把“什么时候少加”“什么时候加满”写出来。写不明白的地方就是你还没有真正吃透的地方。
贪心算法实战：从NOIP经典题“旅行家的预算”看GESP备考策略
1. 一道1999年的NOIP老题凭什么到现在还挂在GESP练习单上在洛谷上搜P1016你会看到题目名字叫“旅行家的预算”来源是NOIP 1999提高组。单论年龄它比现在绝大多数备赛GESP的学生年龄都大。可奇怪的是在很多GESP四、五、六级甚至七级的学习路线清单里这道题都会被反复拎出来。原因很简单它把“读题建模、贪心决策、边界判断、浮点输出”四件事压缩到了一个不超过100行的程序里而这四件事恰好是GESP从四级开始往后每一级都在考察的方向。很多人第一眼看到这道题会以为它是个模拟题一辆车从A到B路上有加油站油箱容量有限求最少花钱。模拟一下每个加油站应该加多少油不就行了真写起来就会发现问题没那么简单——你当前油量不是整数下一站不是只有一个油价又各不相同加多加少直接影响后续所有决策。所以它实际上是“带约束的最优化问题”考察的是贪心策略。从GESP的分级来说四级开始明确要求“能够理解贪心算法的基本思想并解决简单的贪心问题”五级要求“能对贪心策略的正确性进行解释说明”六级及以上则需要在复杂约束下构造正确的贪心模型。P1016恰好横跨了这三个层次。四级的孩子可以把这道题当作“高级模拟”来练哪怕证明不完整五级的孩子必须能说清楚“为什么油箱里还有油时也可能需要继续加油”六级的孩子则应该能自己推出那两个关键分支。做这道题之前比较合理的前置训练线是能熟练使用结构体排序能处理双精度浮点数输出能看懂“无解”型题目的输出约定。如果这三样都还不太稳建议先去做一两道排序和简单模拟的题再回来否则容易把时间浪费在调试语法而不是思考策略上。还有一点值得说这道题的题面很长但信息密度不低。我见过不少学生一看到“计算结果是四舍五入至小数点后两位”就开始慌其实它只是提醒你用固定两位小数输出不存在什么高精度要求。真正容易丢分的反而是那些藏在题干角落里的条件比如“出发时油箱是空的”“油站N可以为零”这类话。2. 题目参数与最优路径到底要算什么2.1 五个输入量和一个清零的油箱题目会给五个量两地距离D1油箱最大容量C每升油能跑的公里数D2出发点的油价P沿途加油站数量N。接着给N行每行两个数该油站离出发点的距离以及该站的每升油价。这里最关键的一句话是“假设出发时油箱是空的”。这意味着你在起点必须至少先买一点油才能走。而且买油只能按“升”思考不是按“钱”思考——你先看需要多少升再决定在哪个站买。需要注意N可以为0。也就是说路上可能一个加油站都没有。这时候别慌直接从起点开车到终点能到就只买“全程耗油量”对应的油不能到就输出No Solution。2.2 样例手算为什么不是“见站就加”洛谷原题的样例是这样的275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2一辆车两地相距275.6公里油箱11.9升每升跑27.4公里起点油价2.8元两个加油站分别距起点102公里和220公里。先算一箱油最多能跑多远11.9 × 27.4 326.06公里比全程长。所以理论上如果起点油价是全程最低加满一箱直接怼到终点都行。但实际情况是220公里处的油价比起点便宜2.2 2.8所以正确的省钱思路是利用220公里处的低价油跑最后一段而不是在起点的2.8元油价上多买。从起点到第二个加油站距离220公里需要的油量是220 ÷ 27.4 ≈ 8.03升。从起点只买这8.03升花 8.03 × 2.8 ≈ 22.48元。到了220公里处油箱里油量已经归零忽略浮点误差。从这个站到终点还剩55.6公里需要 55.6 ÷ 27.4 ≈ 2.03升花 2.03 × 2.2 ≈ 4.47元。合计约 26.95元。第一个加油站设在102公里处油价2.9比起点还贵。最优路线里完全可以不停它哪怕路过也当它不存在。这就是这道题的第一层思考加油站不是“经过就必须消费”而是“只有符合省钱条件才消费”。2.3 把终点当成一个0元虚拟加油站写代码时很多同学的习惯是“循环模拟到最后一个站再单独处理终点”。这个思路没错但会多出一整段特判代码还容易漏。更干净的做法是把终点视为一个虚拟加油站距离设为D1油价设为0。为什么油价设为0因为到达终点之后你不需要再买任何油。而在贪心算法里“价格最低”天然意味着“我一定要尽量少在这个站之前花钱”。把终点油价设为0之后前面所有的“找更便宜的站”逻辑能自动在终点处收口只要终点在当前油量能到达的范围内算法就会选择只加“刚好够到终点”的油量而不是提前加满。这个技巧非常实用在很多最短路和区间覆盖题目里都能用。凡是遇到“最后一个点不是加油站但需要单独处理”的情况加一个虚拟目标点往往能让逻辑统一也减少边界bug。3. 贪心策略的完整推导三种局面对应三个决策3.1 为什么这道题适合贪心而不是动态规划看到“最小费用”四个字很多人第一反应是动态规划。但仔细分析就会发现这个问题的状态非常连续油量是实数不是整数加油站的选择也只受到“能不能到达”的约束而不受之前选择路径的影响。也就是说在当前站点做决策时后续的费用只取决于“我从这里带了多少油出发”“后面油价分布如何”跟之前是怎么到这里的无关。这就是无后效性。更关键的是油价是一个一维序列你只能从左往右开。这么强的线性结构下贪心几乎总是优于DP既节省时间又容易证明。动态规划需要把油量离散化成格点反而引入了大量状态和精度问题属于自己给自己找麻烦。3.2 决策A可达范围内存在比本站更便宜的油站假设我在当前站点油箱加满后能覆盖到后面若干站。如果在这些站里存在一个站的价格比我当前站便宜那我应该怎么买答案不是“买到那个站”而是“一滴不多加只买刚好能开到那个站的油量”。理由很直观既然前面的站更便宜我在当前这个高价站每多买一升就多亏一升的差价。最好的做法就是让低价油站尽可能多承担后续路程的油耗当前高价站的油只用来“够到”低价站即可。还有个细节当“更便宜的站”不止一个时应该选哪一个标准实现里选的是“第一个价格低于当前油价的站”也就是从当前站往后扫描时第一次遇到比本站便宜的站而不是“范围内最便宜的那个”。有人会问如果后面有个特别便宜的站我应该直接跳过这个“第一个便宜站”吗不用。因为即使到了第一个便宜站如果它并不是全局最低算法在那站会继续执行同样的判断找到下一个更便宜的站再只加“刚好够到下一站”的油。这样最终效果是完全等价的而且每次只向前推进一小步程序逻辑更简单。3.3 决策B可达范围内所有油站都比本站贵如果没有一个加油站比当前站便宜那当前站点就是后面这一段里油价最低的。这时候策略完全反过来把油箱加满。为什么会加满而不是只加到够去最便宜的那一站因为以后每一滴油都比现在贵。你在这个站能带走的每一升油都会替代未来某个高价站的油。油箱容量就那么多加的越多节省越多所以必须顶格加满。但加满之后开向哪儿答案是“可达范围内油价最低的那个站”。因为你已经加满了油是满的下一个决策点放在哪里能最大程度降低未来成本当然是最便宜的那个站点。到了那里再重复同样的贪心判断。3.4 无解判断要放在最前面如果当前站点加满油后连下一站都到不了那就是彻底的无解直接输出No Solution。这句话听起来很简单但实际实现中有一半以上的人会在这个环节出错。因为你不能只看“起点到终点能不能一箱油跑完”还要看“每一段相邻加油站之间的距离有没有超过一箱油续航”。只要有一段超过无论怎么规划最终都会在中间抛锚因此必然无解。这个无解检查必须放在主循环之前统一做而不是在循环里发现到不了时才临时输出。统一检查的另一个好处是它可以保证主循环里“当前站点加满后至少能到下一站”这个前提永远成立贪心分支不需要再对“范围为空”做额外处理。4. 完整C实现结构体、排序与主循环4.1 数据建模起点和终点都放进结构体我习惯这样定义#include bits/stdc.h using namespace std; struct Node { double dis; // 离起点的距离 double pri; // 油价 }; int main() { double D1, C, D2, P; int N; cin D1 C D2 P N; vectorNode a; a.push_back({0.0, P}); // 起点距离0油价P for (int i 0; i N; i) { double d, p; cin d p; a.push_back({d, p}); } a.push_back({D1, 0.0}); // 终点距离D1油价0 sort(a.begin(), a.end(), [](const Node x, const Node y) { return x.dis y.dis; });把起点也放进结构体是为了让循环逻辑从“当前位置”出发不需要为起点单独写一份处理代码。把终点当成0元加油站后主循环里最后一站的处理和普通站完全一致。排序在这里是必须的尽管大部分测试数据已经是升序输入但你不能依赖这个约定。4.2 无解预检double maxRun C * D2; for (int i 0; i (int)a.size() - 1; i) { if (a[i 1].dis - a[i].dis maxRun) { cout No Solution endl; return 0; } }这个for循环检查的是“任意相邻两站之间的距离是否超过一箱油续航”。注意排序之后才是相邻所以排序这一步必须放在检查前面。一旦出现某一段距离超标说明无论怎么规划车辆都会在这一段中间耗尽油量直接无解。4.3 主循环与三种决策double oil 0.0; // 当前油量 double ans 0.0; // 总花费 int i 0; // 当前所在加油站的下标 while (i (int)a.size() - 1) { int cheaper -1; // 第一个比当前油价更便宜的站 int minPos -1; // 可达范围内油价最低的站 for (int j i 1; j (int)a.size(); j) { if (a[j].dis - a[i].dis maxRun) break; if (minPos -1 || a[j].pri a[minPos].pri) { minPos j; } if (cheaper -1 a[j].pri a[i].pri) { cheaper j; } } if (cheaper ! -1) { // 决策A只加刚好能到 cheaper 站的油 double need (a[cheaper].dis - a[i].dis) / D2; if (need - oil 1e-9) { ans (need - oil) * a[i].pri; oil need; } oil - need; i cheaper; } else { // 决策B本站加满然后去范围内最便宜的站 ans (C - oil) * a[i].pri; oil C; double need (a[minPos].dis - a[i].dis) / D2; oil - need; i minPos; } } printf(%.2f\n, ans); return 0; }这段代码的主循环终止条件是i到达终点虚拟站。由于终点油价是0从任意非终点站出发终点一定是“更便宜站点”的候选所以算法不会在错误的时间进入决策B。只有当终点不在当前油量加满后的可达范围内时才会真的执行“加满并去范围最低站点”的分支。4.4 复杂度够不够用这个程序最外层循环是O(N)个决策点每个决策点内部会扫描后面所有站点因此最坏复杂度是O(N²)。原题N最多100O(N²)绰绰有余。GESP的代码提交环境中这样的复杂度也完全能过。即使N放大到1000O(N²)也就是百万级运算依然没问题。如果非要进一步优化可以在排序后用一个单调栈或双指针维护“下一个更低价格的位置”把复杂度降到O(N log N)但对这道题来说属于过度设计。竞赛里“能过就是好代码”不需要追求理论上的极致。5. “No Solution”判定顺序与浮点数精度陷阱5.1 先排序再检查相邻站距离无解检查的前提是“相邻”。如果输入数据没有按距离排好序直接检查输入顺序里的相邻站结果一定是错的。虽然题目通常保证加油站按距离递增给出但你不能赌。尤其是自己造数据测试的时候一定要先排序。这个看似无关紧要的小步骤能避免一堆莫名其妙的问题。还有一个小细节排序后如果出现距离相同的站点处理时要有心理准备。虽然原题几乎不会这样出但如果你自己扩展练习重复距离会让“相邻站距离为0”预检不会报错但主循环里需要判断是哪个站更便宜。我一般遇到这种情况会在排序比较器里额外规定距离相同时油价低的排前面。这样即使数据里有重复位置贪心逻辑也能自动选择更优价格。5.2 N0的情况当N0时输入里不会出现任何加油站。处理起来很简单先是起点和终点两个点放进结构体排序后两个点相邻。如果D1 C × D2无解否则从起点只买D1/D2升油费用是D1/D2 × P。用上文代码跑N0也完全没问题a里只有起点和终点两个元素预检检查两点距离是否超过maxRun主循环里从起点出发终点价格0一定小于起点价格P于是进入决策A加刚好够到终点的油。所以不需要单独写特判。5.3 double比较和输出格式这题所有数字都用double来存不要用float否则可能在边界距离上翻车。比较两个浮点数大小尽量不要写成x y这种直接判断而是用x - y 1e-9之类的容差比较。输出时用printf(%.2f\n, ans)或者cout fixed setprecision(2) ans endl;注意要保留两位小数。这里的四舍五入并不是要求你手写标准格式化输出会自动处理。有个细节值得提醒题目描述里写的“计算结果四舍五入至小数点后两位”在实际评测中就是要求精确输出两位小数。不要自己额外做任何“四舍五入”操作避免二次舍入误差。5.4 一个容易忽略的浮点场景当油量计算出现“刚好够到下一站”的情况时浮点误差可能让程序认为差一点点于是多买了0.0000001升油。这通常不会影响最终答案的两位小数输出但如果某个测试点数据恰好卡在边界上可能就会出现微小偏差。稳妥的做法是在判断if (oil need)时改为if (need - oil 1e-9)这样既保留真实比较语义又避免了浮点噪声带来的误判。代码里其他浮点比较也建议统一加上这个容差。5.5 实践中的自测数据写完代码后我一般会准备几组自测数据// 例1起点加满10L到50公里处油价4元的加油站再加5L到终点 // 输入 100 10 10 5 1 50 4 // 输出应该是70.00 // 例2一箱油根本撑不到下一个站 // 输入 100 10 5 5 1 60 4 // 10*550 60输出 No Solution // 例3全程不需要加油 // 输入 50 10 10 5 0 // 输出 25.00 // 例4中间全是贵的油起点加满直接跑 // 输入 100 10 10 5 1 10 100 // 起点加满10L花50终到答案50.00例4很多人会写错因为10公里处有个天价加油站但到终点需要10升油一箱油正好够所以完全不用理它。正确输出是50.00而不是“在起点只加10公里的油然后去天价站”。6. 从NOIP到GESP一道题拆出四级、五级、六级三种考法6.1 四级视角把贪心当高级模拟来练GESP四级的大纲里“贪心”并不是一个特别深的考点更多是让你接触“每一步都做当前最优选择”这个思想。P1016恰好能承担这个角色。如果孩子只学到四级我建议先不要给他们讲“决策A/B的完整证明”而是让他们先看懂代码流程先检查能不能到再在每个站找后面有没有更便宜的站。有就少加没有就加满。这个口诀足够他们把这个题调通。调通之后可以做几道类似结构的题做迁移训练比如简单的区间选点、部分背包。它们都在强调同一个道理局部最优能推出全局最优的条件是什么。四级的孩子能意识到这一点就已经超过很多“只会写模板”的同龄选手了。6.2 五级视角必须能解释“为什么这么做是对的”到了GESP五级单纯能AC是不够的评委会看你能不能把策略讲清楚。这时候需要做一些更扎实的证明训练。反证法是最好用的证明方式。比如决策A如果在当前高价站多买了油而后面有低价站那么这多买的油本来可以在低价站买因此当前方案一定不是最优所以“只买刚好够到低价站”才是最优。决策B的证明思路类似后面所有站都更贵在当前站少买了一升未来就得在更贵的站补一升总费用只会增加所以必须加满。这个“反证交换论证”的思维是五级和四级在同一个题目上的关键分水岭。写题解、画图、给同学讲题都是不错的训练方式。如果只是闷头刷题很难真正过渡到“会证明”的层次。6.3 六级以上视角把单点决策抽象成普适模型到六级以后题目不会只考课本原题而会换皮。比如把“油箱容量”改成“电池容量”把“油价”改成“充电价格”甚至把“单程”改成“可以回头”你就需要重新设计贪心决策。P1016真正的价值在于它提供了一个非常好的“多约束贪心”模板在某个可决策节点上如何利用范围枚举选择下一步目标。这个模板在后续的很多题里都能复现比如带往返运输的最小费用、带容量限制的区间覆盖、甚至某些资源调度问题。六级及以上的备赛不应该满足于背题解而是要尝试自己改题。我带的不少学生会在做完P1016之后自己加一两个限制条件再问自己怎么做。这种训练对GESP七、八级以及后续冲击更高赛事的帮助往往比多刷十道类似题更有效。6.4 推荐练习顺序如果要从零开始挑战这道题我给一条比较顺的路线先用30分钟自己思考画出能到达的站点范围图。看一遍标准代码的框架不急着看全先把“无解检查”和“主循环”的边界搞清楚。自己敲一遍跑通样例。把样例手算一遍确认结果对得上。自己构造3-4个边界测试点尤其是“N0”“一箱油刚好到”“中间有很贵的站”这几类。尝试不看代码用文字把贪心策略写出来。这套流程走完这道题才算真正吃透。7. 写完之后我沉淀下的几条实操体会第一这道题最容易被低估的地方是“读题”。很多学生第一遍看完题面以为只需要在“最便宜的加油站加满油”就够了样例都能过但一提交就只能拿到部分分。真正把“每个站点的油量状态”当作连续量来理解和建模才是这道题的核心门槛。第二代码里不要写“看起来很聪明”的优化。比如有人会在主循环里反复做浮点运算优化或把油价做一大堆常数处理。这些在这个数据范围下都毫无意义反而容易引入精度错误。保持简单、直接、容差到位是我在这道题上最推荐的写法。第三如果调试时发现输出只差0.01先别急着怀疑算法先检查是不是格式化输出写错了或者某一处直接用比较了浮点数。我见过太多因为这两点被卡半小时的情况。第四这道题对一个备赛者最宝贵的训练不是“学会了贪心”而是“建立起了从题面提取约束条件、抽象成数学模型、写代码、造数据验证”的完整闭环。GESP从四级到六级每一级都在反复强化这条链路。把这套方法论练稳了比多刷十道题更管用。我个人的习惯是每带一批学生刷P1016都会要求他们提交完AC后再写一段不超过200字的“解题说明”强迫自己把决策A和决策B的逻辑用大白话讲清楚。这个习惯后来帮他们在GESP五级、六级里解决了很多需要“解释设计思路”的题型。如果你也是自己备考而不是跟班学建议同样试试这个办法AC之后合上代码用两段话把“什么时候少加”“什么时候加满”写出来。写不明白的地方就是你还没有真正吃透的地方。