1. 题目背景与问题解析这道来自浙江大学的编程试题To Fill or Not to Fill看似简单实则蕴含了典型的贪心算法应用场景。题目描述了一个经典的汽车加油问题给定一条高速公路上的加油站分布、各站油价以及汽车的油箱容量要求计算出从起点到终点的最低加油成本。在实际生活中这个问题对应着长途驾驶时的加油策略选择。比如我从杭州开车去北京沿途有多个加油站油价各不相同我的油箱最多能跑500公里。那么应该在哪些加油站加油、加多少油才能花最少的钱到达目的地这就是本题要解决的核心问题。2. 问题建模与算法选择2.1 输入参数定义首先我们需要明确题目的输入参数油箱最大容量Cmax单位升总距离D单位公里每升油可行驶距离Davg单位公里/升加油站数量N每个加油站的油价和距离起点的位置通过这些参数我们可以计算出满箱油能跑的最远距离 Cmax * Davg从当前加油站到下一站的距离差2.2 贪心算法思路这个问题适合采用贪心算法解决因为每个加油决策只需要考虑当前最优选择而不需要考虑全局。具体思路是按距离排序所有加油站包括起点和终点从起点出发在可达范围内寻找油价最低的加油站计算需要加多少油才能到达那个加油站重复上述过程直到终点关键点在于每次都在当前油量能到达的范围内选择油价最低的加油站进行加油。3. 详细算法实现3.1 数据结构设计首先我们需要设计合适的数据结构来存储加油站信息class GasStation: def __init__(self, price, distance): self.price price # 每升油价 self.distance distance # 距离起点的距离然后读取输入数据并初始化加油站列表def read_input(): Cmax, D, Davg, N map(float, input().split()) N int(N) stations [] for _ in range(N): price, dist map(float, input().split()) stations.append(GasStation(price, dist)) # 添加终点作为最后一个加油站 stations.append(GasStation(0, D)) # 按距离排序 stations.sort(keylambda x: x.distance) return Cmax, D, Davg, stations3.2 核心算法实现下面是贪心算法的主要实现逻辑def calculate_min_cost(Cmax, D, Davg, stations): max_distance Cmax * Davg # 满油能跑的最远距离 current_pos 0.0 # 当前位置 current_gas 0.0 # 当前油量 total_cost 0.0 for i in range(len(stations)): # 检查是否能到达这个加油站 if stations[i].distance current_pos max_distance: # 无法到达下一个加油站 print(The maximum travel distance %.2f % (current_pos max_distance)) return # 在当前能到达的范围内寻找油价更低的加油站 min_price float(inf) min_index -1 for j in range(i, len(stations)): if stations[j].distance current_pos max_distance: break if stations[j].price min_price: min_price stations[j].price min_index j # 如果找到比当前油价更低的直接去那里 if min_price stations[i].price: break # 计算需要加多少油 distance_to_go stations[min_index].distance - current_pos gas_needed distance_to_go / Davg if min_price stations[i].price: # 直接去更便宜的加油站只加刚好够的油 add_gas max(0.0, gas_needed - current_gas) total_cost add_gas * stations[i].price current_gas max(current_gas, gas_needed) - gas_needed else: # 没有更便宜的加满油 add_gas Cmax - current_gas total_cost add_gas * stations[i].price current_gas Cmax - gas_needed current_pos stations[min_index].distance i min_index # 跳到选择的加油站 print(%.2f % total_cost)3.3 算法复杂度分析该算法的时间复杂度主要由两部分组成排序加油站O(N log N)主循环中的嵌套循环最坏情况下O(N^2)在实际道路场景中加油站数量N通常不大因此这个复杂度是可以接受的。对于编程竞赛来说N的规模一般会限制在合理范围内。4. 边界条件与特殊情况处理4.1 无法到达终点的情况在算法实现中我们已经处理了无法到达下一个加油站的情况这时会输出最远能到达的距离。但还需要考虑一些特殊情况起点没有加油站题目通常保证起点有加油站两个加油站之间的距离超过满油行驶距离已在代码中处理终点距离最后一个加油站超过满油行驶距离需要特别检查4.2 精度问题处理由于涉及浮点数计算需要注意精度问题比较距离时使用小的epsilon值输出保留两位小数避免累积误差改进的距离比较可以这样写epsilon 1e-7 if stations[i].distance current_pos max_distance epsilon: print(The maximum travel distance %.2f % (current_pos max_distance)) return5. 算法优化与变种5.1 使用优先队列优化原始的嵌套循环查找最低油价可以优化为使用优先队列堆将时间复杂度从O(N^2)降低到O(N log N)import heapq def optimized_calculate_min_cost(Cmax, D, Davg, stations): max_distance Cmax * Davg current_pos 0.0 current_gas 0.0 total_cost 0.0 heap [] i 0 while current_pos D - 1e-7: # 考虑浮点精度 # 将当前能到达的所有加油站加入堆 while i len(stations) and stations[i].distance current_pos max_distance 1e-7: heapq.heappush(heap, (stations[i].price, stations[i].distance)) i 1 if not heap: # 无法到达下一个加油站 print(The maximum travel distance %.2f % (current_pos max_distance)) return # 取出油价最低的加油站 min_price, min_dist heapq.heappop(heap) # 计算需要多少油到达那里 distance_to_go min_dist - current_pos gas_needed distance_to_go / Davg if current_gas gas_needed: # 需要加油 add_gas gas_needed - current_gas total_cost add_gas * min_price current_gas 0 else: # 有足够油量不需要加油 current_gas - gas_needed current_pos min_dist print(%.2f % total_cost)5.2 问题变种思考这个问题有几个有趣的变种加油站有开放时间限制需要增加时间维度不同加油站油品不同影响油耗和价格电动车充电站问题充电时间成为考虑因素6. 实际应用与扩展6.1 现实生活中的加油策略这个算法可以直接应用于现实生活中的长途驾驶加油规划。在实际使用时还需要考虑加油站品牌偏好休息时间安排交通状况影响油价波动趋势6.2 其他类似场景类似的贪心算法应用场景包括任务调度问题背包问题的某些变种资源分配问题网络路由选择6.3 算法竞赛中的应用在编程竞赛中这类问题经常出现常见的变种包括增加时间限制多车辆协同动态油价变化部分加油站不可用掌握这个基础问题的解法可以帮助快速解决类似的竞赛题目。