提交时间:2026-01-18 20:55:36
运行 ID: 83005
def main(): import sys # 读取输入数据 data = list(map(float, sys.stdin.readline().split())) D1 = data[0] # 两个城市总距离 C = data[1] # 油箱容量 D2 = data[2] # 每升汽油能行驶的距离 P0 = data[3] # 出发点油价 N = int(data[4]) # 沿途油站数 # 存储加油站信息:(距离, 油价),先加入出发点 stations = [(0.0, P0)] for _ in range(N): di, pi = map(float, sys.stdin.readline().split()) stations.append((di, pi)) # 加入终点作为虚拟加油站(油价为0) stations.append((D1, 0.0)) # 按距离排序(处理输入可能无序的情况) stations.sort(key=lambda x: x[0]) # 检查输入合法性:是否有加油站距离超过总距离,或距离递减 for i in range(1, len(stations)): if stations[i][0] > D1 or stations[i][0] <= stations[i-1][0]: print("No Solution") return current_station = 0 # 当前所在加油站索引 current_oil = 0.0 # 当前油箱油量 total_cost = 0.0 # 总费用 max_distance_per_tank = C * D2 # 油箱加满能跑的最大距离 # 循环直到到达终点 while current_station < len(stations) - 1: # 当前加油站信息 curr_dist, curr_price = stations[current_station] # 检查是否能到达下一个加油站(基础可达性) next_dist = stations[current_station + 1][0] if next_dist - curr_dist > max_distance_per_tank: print("No Solution") return # 在可达范围内找最便宜的加油站 min_price = curr_price min_price_index = current_station reachable = False # 遍历所有可达的加油站 for i in range(current_station + 1, len(stations)): dist = stations[i][0] # 超出油箱最大续航,停止遍历 if dist - curr_dist > max_distance_per_tank: break # 找到更便宜的加油站 if stations[i][1] < min_price: min_price = stations[i][1] min_price_index = i reachable = True break # 找到第一个更便宜的就可以,贪心选择 # 如果没找到更便宜的(当前就是范围内最便宜的) if min_price_index == current_station: # 加满油箱,开到下一个加油站 need_oil = C - current_oil total_cost += need_oil * curr_price current_oil = C # 行驶到下一个加油站 next_station = current_station + 1 drive_dist = stations[next_station][0] - curr_dist current_oil -= drive_dist / D2 current_station = next_station else: # 找到更便宜的加油站,计算需要加的油量 target_dist = stations[min_price_index][0] # 到达目标加油站需要的油量 need_oil_total = (target_dist - curr_dist) / D2 # 需要补充的油量 need_oil = need_oil_total - current_oil if need_oil > 0: total_cost += need_oil * curr_price current_oil = need_oil_total # 行驶到目标加油站 drive_dist = target_dist - curr_dist current_oil -= drive_dist / D2 current_station = min_price_index # 输出结果,四舍五入到两位小数 print("{0:.2f}".format(round(total_cost, 2))) if __name__ == "__main__": main()