1. 题目背景与核心问题解析
这道来自浙江大学的编程试题"To Fill or Not to Fill"看似简单，实则蕴含了典型的贪心算法应用场景。题目模拟了现实中的汽车加油决策问题：给定一条高速公路上的多个加油站位置和油价信息，以及汽车的油箱容量和起始/终点位置，计算出完成旅程的最低油费方案。
在实际解题过程中，我发现这个题目完美复现了长途驾驶时的经典困境：当前加油站油价较贵，但油箱里的油还能跑一段距离，是选择现在加满油，还是赌前方有更便宜的加油站？这种"加油博弈"正是贪心算法在实际生活中的生动体现。
2. 问题建模与算法选择
2.1 输入参数分析
题目通常提供以下关键参数：
- Cmax：油箱最大容量（单位：升）
- D：起点到终点的总距离（单位：公里）
- Davg：汽车每升油可行驶的里程
- N：沿途加油站数量
- 每个加油站的Pi（油价）和Di（距离起点的位置）
2.2 核心算法决策
经过多次实践验证，贪心算法在此类问题中表现出色。其核心思路是：在当前加油站，做出局部最优选择——即在可达范围内，寻找油价最低的加油站进行加油。这种策略虽然看似短视，但通过数学证明可以确保全局最优。
重要提示：必须严格验证贪心选择性质，确保局部最优能推导出全局最优。这是使用贪心算法的前提条件。
3. 详细解题步骤实现
3.1 数据预处理
# 示例数据结构 stations = [ {"dist": 0, "price": 7.0}, # 起点加油站 {"dist": 150, "price": 6.5}, {"dist": 300, "price": 7.1}, {"dist": 450, "price": 6.0} # 终点加油站 ] stations.sort(key=lambda x: x["dist"]) # 按距离排序3.2 主算法流程
- 初始化当前油量（0）、当前位置（起点）、总花费（0）
- 循环直到到达终点： a. 找出当前油量可达范围内的所有加油站 b. 如果范围内有更便宜的加油站：
- 只加到刚好能到达该站的油量 c. 如果范围内没有更便宜的：
- 在当前站加满油
- 选择范围内油价最低的站作为下一站
- 处理无法到达终点的情况
3.3 边界条件处理
- 起点无加油站：直接返回不可达
- 相邻加油站间距超过满油行驶距离：直接返回不可达
- 终点不在最后一个加油站：需要特殊处理
4. 代码实现与优化技巧
4.1 基础实现框架
def calculate_min_cost(Cmax, D, Davg, stations): max_distance = Cmax * Davg current_fuel = 0 current_pos = 0 total_cost = 0 while current_pos < D: reachable = [s for s in stations if s["dist"] > current_pos and s["dist"] <= current_pos + max_distance] if not reachable and current_pos + max_distance < D: return "无法到达终点" # 找出可达范围内比当前站便宜的加油站 cheaper = [s for s in reachable if s["price"] < current_price] if cheaper: next_station = min(cheaper, key=lambda x: x["dist"]) needed = (next_station["dist"] - current_pos) / Davg if current_fuel < needed: add = needed - current_fuel total_cost += add * current_price current_fuel = 0 else: current_fuel -= needed current_pos = next_station["dist"] else: # 加满油并选择范围内最便宜的站 if current_pos + max_distance >= D: needed = (D - current_pos) / Davg total_cost += max(0, (needed - current_fuel)) * current_price return total_cost else: next_station = min(reachable, key=lambda x: x["price"]) total_cost += (Cmax - current_fuel) * current_price current_fuel = Cmax - (next_station["dist"] - current_pos)/Davg current_pos = next_station["dist"] return total_cost4.2 性能优化要点
- 预处理阶段对加油站按距离排序（O(N log N)）
- 使用双指针法寻找可达范围，避免每次全量扫描
- 提前终止条件判断，避免无效计算
- 浮点数比较使用误差范围而非直接相等
5. 常见错误与调试技巧
5.1 典型错误案例
- 未考虑起点就是加油站的情况
- 忽略了油箱可能有初始油量（题目通常假设为空）
- 浮点数精度问题导致比较错误
- 没有处理终点不是加油站的特殊情况
5.2 调试建议
- 先用手算小规模测试用例验证算法逻辑
- 打印关键决策点的变量状态（当前位置、剩余油量、总花费）
- 特别注意边界条件测试：
- 起点和终点重合
- 只有一个加油站
- 所有加油站油价相同
- 需要加满油才能到达下一站的情况
6. 算法扩展与实际应用
6.1 变种问题思考
- 加入加油站等待时间成本
- 考虑不同油品类型（如92#、95#汽油）
- 电动车充电站规划问题（充电时间非线性）
- 引入交通拥堵因素影响实际行驶距离
6.2 实际工程应用
这类算法不仅用于ACM竞赛，在实际的导航软件、物流路径规划系统中都有广泛应用。例如某知名地图App的"智能加油提醒"功能，其核心算法就与此题高度相似，只是加入了实时油价数据、用户偏好等更多维度。
我在实际开发类似系统时，发现还需要考虑以下工程因素：
- 实时油价API的响应时间和缓存策略
- 用户车辆的实际油耗曲线（非恒定Davg）
- 加油站营业时间等限制条件
- 多目标优化（时间成本 vs 油费成本）
7. 个人实战经验分享
在多次实现这个算法的过程中，我总结出几个关键心得：
贪心证明很重要：最初我直接套用贪心思路，但总在某些测试用例失败。后来发现必须严格证明"局部最优导致全局最优"的性质。对于本题，关键在于油价的可比性和加油量的连续性。
浮点处理要谨慎：曾因为直接比较浮点数相等而导致判断错误。现在统一使用
abs(a-b) < 1e-6的方式进行比较。测试用例设计：建议准备以下测试组合：
- 普通案例（3-5个加油站）
- 极端案例（只有起点和终点）
- 大数案例（距离很远但油箱很大）
- 油价单调递增/递减的特殊情况
代码可读性技巧：将主算法分解为几个清晰的子函数：
find_reachable_stations()find_cheaper_station()calculate_fuel_needed()这样即使算法复杂，代码结构依然清晰。
