P1016 [NOIP 1999 提高组] 旅行家的预算-牛翰网

这是一道经典的贪心算法问题。它考验的不仅仅是找到一个看似正确的贪心策略，更是对策略背后逻辑的严谨思考，以及对问题状态的完整建模。很多同学（包括你最初的代码）都会掉入同一个陷阱，这篇题解将带你绕开它。

问题描述

一辆汽车需要从起点行驶到终点，途中有若干加油站。给定汽车油箱容量、每升油能行驶的距离、以及每个加油站的油价和位置。目标是计算从起点到终点所需的最小花费。如果无法到达，则输出 “No Solution”。

核心思想：贪心策略的正确打开方式

贪心算法的精髓在于每一步都做出当前看起来最优的选择。那么，在这个问题里，当车停在某个加油站 i 时，“最优选择”到底是什么？

这需要分两种情况讨论：

情况一：在满油可达范围内，有比当前油站 `i` 更便宜的油站

决策：既然前方有更便宜的油，我们显然不应该在当前这个较贵的站点加太多油。加多少最合适？刚好能开到那个最近的、比当前便宜的油站 j 即可。
理由：我们的目标是尽快用上更便宜的油。任何在当前站多加的、超出到达 j 站所需的油，都是在用“更贵的成本”行驶本可以由“更便宜成本”覆盖的距离，这显然不划算。

情况二：在满油可达范围内，所有油站都比当前油站 `i` 贵（或一样贵）

决策：这说明当前站 i 的油是接下来一段路程中最划算的了。我们应该充分利用这个优势。所以，应该在当前站把油箱加满，然后径直开往这个可达范围内油价最低的那个油站 k。
理由：通过加满油，我们用当前相对便宜的油，行驶了最远的距离，最大限度地减少了未来在更贵的油站加油的需求。选择去 k 站，是为了让下一次决策时，我们的起点油价尽可能低。

警示录：常见的错误陷阱

陷阱一：忽略“剩余油量”，导致错误的成本计算（这是你代码的根本问题）

我最初的代码逻辑是：从站 i 找到目标站 j，然后计算 (a[j].dis - a[i].dis) * a[i].co / per 作为花费。这个公式隐含了一个致命的假设：每次出发时油箱都是空的。

【致命场景】

A站（dist=0, price=5.0），B站（dist=400, price=10.0），终点C（dist=600）。
油箱50升，每升跑10公里。满油跑500公里。

错误逻辑：
- 在A站，只能去B站。花费 (400/10) * 5.0 = 200 元。
- 到达B站后（假设油箱空了），要去C站。花费 (200/10) * 10.0 = 200 元。
- 总花费：400元。
正确逻辑：
- 在A站，发现前方B站更贵。决策：加满油。花费 50 * 5.0 = 250 元。油箱现有50升。
- 开车去B站，消耗40升油。到达B站时，油箱还剩10升！
- 在B站，到终点C需要20升油。因为油箱里有10升，所以只需要再买10升昂贵的油。花费 10 * 10.0 = 100 元。
- 总花费：250元（A站加油） + 100元（B站加油） = 350元。

结论： 如果不追踪 current_oil（当前油量）这个状态，你的算法永远无法做出“用之前剩下的便宜油”这种决策，从而导致计算结果偏高。

陷阱二：错误的贪心目标

我最初代码的另一个问题是，在所有可达站里，总是选择那个油价最低的。这在某些情况下不是最优的。正确的做法是区分上述两种情况，做出不同的决策。

建模与实现

为了优雅地实现正确的贪心策略，我们可以做一些巧妙的建模：

统一站点：将起点和终点都视为特殊的“加油站”。
- 起点的距离为0，油价为初始油价。
- 终点的距离为总距离，油价设为0（这能确保它总会被优先考虑，逻辑统一）。
排序：将所有站点（包括起点和终点）放入一个列表，并按距离从小到大排序。
追踪状态：在循环中，必须维护 current_oil 和 total_cost 两个核心变量。

参考代码实现

import sys
class Oil:
    def __init__(self, co=0, dis=0):
        self.co = co
        self.dis = dis
input = lambda: sys.stdin.readline().strip()
dis, c, per, start_co, n = map(float, input().split())
n, maxn, a = int(n), c * per, [Oil(start_co, dis=0)] 
for i in range(n):
    x, y = map(float, input().split())
    a.append(Oil(y, x))
a.append(Oil(co=0, dis=dis))
a.sort(key=lambda item: item.dis)
n = len(a) - 1
if a[0].dis or a[1].dis - a[0].dis > maxn:
    print("No Solution")
    exit()
i, total_cost, current_oil = 0 , 0.0, 0.0
while i < n: 
    has_cheaper_station = False
    for j in range(i + 1, n + 1):
        if a[j].dis - a[i].dis > maxn:
            break
        if a[j].co < a[i].co:
            dist_to_j = a[j].dis - a[i].dis
            oil_needed = dist_to_j / per
            if current_oil < oil_needed:
                oil_to_buy = oil_needed - current_oil
                total_cost += oil_to_buy * a[i].co
                current_oil += oil_to_buy
            current_oil -= oil_needed
            i, has_cheaper_station = j, True
            break
    if has_cheaper_station: continue
    cheapest_next_idx = -1
    min_price_in_range = float('inf')
    for j in range(i + 1, n + 1):
        if a[j].dis - a[i].dis > maxn:
            break
        if a[j].co < min_price_in_range:
            min_price_in_range, cheapest_next_idx = a[j].co, j
    if cheapest_next_idx == -1:
        print("No Solution")
        exit()
    oil_to_buy = c - current_oil
    total_cost += oil_to_buy * a[i].co
    current_oil, dist_to_target = c, a[cheapest_next_idx].dis - a[i].dis
    oil_needed, i = dist_to_target / per, cheapest_next_idx
    current_oil -= oil_needed
print("%.2f" % total_cost)