Solutions CS101

Appearance

M20134: 鹅腿阿姨送鹅腿 ​

greedy, http://cs101.openjudge.cn/routine/20134/

在北京大学校园里，鹅腿阿姨凭借其出色的手艺，制作的“阿姨牌鹅腿”声誉满天下。每天，阿姨都会收到来自全国各地的鹅腿订单。

一天，远在新疆的羊肉串叔叔买买提明·买买提打算品尝一下这道传奇美味。于是，他在鹅腿微信群里发送了一个 15 元的红包，并附言：“辣腿一个”。

收到红包后，敬业的鹅腿阿姨连夜制作了一只热腾腾的辣味鹅腿，并决定亲自驾车将这份美味送到买买提明·买买提的手中。然而，买买提明·买买提的家位于：

新疆维吾尔自治区伊犁哈萨克自治州塔城地区和布克赛尔蒙古自治县和什托洛盖镇西特木恩哈布奇克村

该地距离鹅腿阿姨所在的北京大学足足有 d1 千米之遥！但这并不能阻挡敬业的鹅腿阿姨。

已知鹅腿阿姨的汽车油箱容量为 c 升，每升汽油可供汽车行驶 d2 千米。从北京大学到西特木恩哈布奇克村的途中共有 n 个加油站。

其中，第 i 个加油站与北京大学（起点）的距离为 di 千米，该加油站的油价为每升 pi 元。出发点（北京大学）处的汽油价格为每升 m 元。出发时，汽车的油箱是空的。

请计算鹅腿阿姨能否将鹅腿顺利送到买买提明·买买提手上。如果可以，请问至少需要花费多少油钱？（当然，这笔旅途油费最终将由买买提明·买买提全额报销）

数据范围与约定

0 < d1 <= 10^5 （总距离，千米），0 < c <= 1000 （油箱容量，升），

0 < d2 <= 1000 （每升汽油行驶距离，千米），0 < m, pi <= 1000 （汽油价格，元/升），

0 <= n <= 5000 （中途加油站数量，整数），0 <= di <= d1 （加油站到起点的距离，千米）

输入

输入共 n + 1 行。 第一行包含五个数值：d1, c, d2, m, n。其中 n 为整数，其余均为浮点数。 接下来的 n 行，每行包含两个浮点数 di 和 pi，分别表示第 i 号加油站离出发点的距离（千米）与该加油站每升汽油的价格（元）。

输出

如果可以送达目的地，输出一个实数，表示最小的油费开销，保留两位小数。 如果由于油箱容量限制，中途无法到达下一个加油站或最终目的地，则输出 No Solution。

样例输入

Sample1 Input:
475.6  11.9  27.4  14.98  6
102.0  9.99 
220.0  13.29
256.3  14.79
275.0  10.29
277.6  11.29
381.8  10.09

Sample1 Output:
192.15

样例输出

Sample2 Input:
50 30 2 16 6
5 19
17 20
13 14
27 7.85
44 114514
49.99 0.1

Sample2 Output:
292.24

提示：greedy

  1. 途中加油站的输入顺序不一定是按照距离起点的顺序排列，处理前需先进行排序。
  2. 运算过程中建议使用双精度浮点数（Python 中默认的 float），以避免精度的累积误差。

来源：cs101-2019 姜铖

利用了区间覆盖（Interval Coverage）的思想，将“油箱容量限制”巧妙地转化为“每个加油站可覆盖的最大距离区间”。

python
import sys
import heapq

def solve():
    # 使用 sys.stdin.read 快速读取，防止因多行输入导致 EOF 错误
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    d1 = float(input_data[0])
    c = float(input_data[1])
    d2 = float(input_data[2])
    m = float(input_data[3])
    n = int(input_data[4])

    # 初始状态：堆中只有起点（价格 m，位置 0）
    heap = [(m, 0.0)]
    d0 = 0.0  # 当前已经计算过花费的覆盖终点
    tot = 0.0 # 最小总油费
    max_range = c * d2  # 单次加满油能行驶的最大距离

    # 解析所有中途加油站的数据
    stations = []
    idx = 5
    for _ in range(n):
        di = float(input_data[idx])
        pi = float(input_data[idx+1])
        idx += 2
        if di < d1:  # 忽略超过终点的无用加油站
            stations.append((di, pi))

    # 按距离升序排序，并追加终点（终点距离为 d1，油价设为无穷大，表示不在此加油）
    sta = sorted(stations) + [(d1, float("inf"))]

    for d, p in sta:
        # 当堆顶的加油站由于距离太远，其最大辐射范围（heap[0][1] + max_range）无法到达当前站 d 时
        while heap and heap[0][1] + max_range < d:
            # 在将其从堆中弹出之前，要“物尽其用”
            # 如果该便宜加油站的最大辐射范围超过了当前已覆盖的终点 d0
            if heap[0][1] + max_range > d0:
                # 尽量用该便宜油覆盖 [d0, 辐射上限] 这段区间
                tot += (heap[0][1] + max_range - d0) / d2 * heap[0][0]
                d0 = heap[0][1] + max_range
            # 彻底无法辐射到当前站 d，将其弹出
            heapq.heappop(heap)

        # 如果堆空了，说明没有任何已通过的加油站能够辐射到当前站 d，即无解
        if not heap:
            print("No Solution")
            return

        # 用当前堆顶最便宜的加油站，将未覆盖的区间 [d0, d] 填满
        tot += (d - d0) / d2 * heap[0][0]
        
        # 将当前加油站放入堆中，用于后续路段的决策
        heapq.heappush(heap, (p, d))
        d0 = d

    print(f"{tot:.2f}")

if __name__ == '__main__':
    solve()

该算法的核心思想是将“油箱存量模拟”抽象为“用最便宜的可用油覆盖路程区间”：

  1. 区间 [d0,d] 的填补： 当需要从上一个状态的覆盖点 d0 推进到当前加油站 d 时，不需要考虑复杂的“加多少油”的物理过程，而是直接在当前所有可用的、能辐射到 d 的历史加油站中，挑出最便宜的一个（即最小堆的堆顶 heap[0]），来全额支付这一段路程 [d0,d] 所需的油费。

  2. 最大范围限制（heap[0][1] + c*d2 < d）： 一个在 Sd 处的加油站，即使加满油也最多只能让我们走到 Sd+c×d2。如果当前要去的站点 d 已经超过了这个上限，那么这个加油站就绝对无法用来支付通往 d 的路费了。

  3. 弹出堆顶时的“物尽其用”： 在把一个便宜的加油站 heap[0] 丢弃之前，如果它的最大辐射范围比当前计算到的位置 d0 还要远，应该“贪心”地认为，在之前通过它时其实已经把油箱加满了。因此，用它便宜的价格把到它辐射上限为止的所有剩余空间全部填满，最大化利用它的低油价。

这是一道经典的贪心算法问题（通常被称为“旅行家的预算”或“汽车加油问题”）。

算法思路

可以将起点看作第 0 个加油站（距离为 0，油价为 m），终点看作第 n+1 个加油站（距离为 d1，油价为 0）。

从当前加油站 i 出发，汽车在油箱满载状态下能行驶的最大距离为 Dmax=c×d2。我们面临以下几种情况：

  1. 若在行驶能达到的范围内（即距离 ≤Dmax），存在油价低于当前加油站 i 的加油站：

    • 应该找到第一个油价低于 pi 的加油站 j。
    • 为了以最便宜的开销到达 j，只需要让油箱里的油刚好足够支撑到 j。如果当前油量不够，就在 i 站补充到刚好能到达 j 的油量；如果当前油量已经足够，则不加油。
    • 随后驾车前往 j，将 j 设为新的当前站点。

  2. 若在行驶能达到的范围内，所有加油站的油价都比当前加油站 i 贵：

    • 既然当前站 i 的油价是最便宜的，应当在 i 站将油箱加满。
    • 然后驾车前往距离最近的下一个加油站 i+1，在 i+1 站重新进行决策（此时油箱里会剩下不少在 i 站购买的便宜油）。

  3. 无法到达下一站：

    • 如果相邻两个加油站之间的距离大于 Dmax，则无论如何也无法到达终点，输出 No Solution。

Python 实现代码

python
import sys

def solve():
    # 读取所有输入数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    d1 = float(input_data[0])
    c = float(input_data[1])
    d2 = float(input_data[2])
    m = float(input_data[3])
    n = int(input_data[4])

    raw_stations = []
    idx = 5
    for _ in range(n):
        di = float(input_data[idx])
        pi = float(input_data[idx+1])
        idx += 2
        # 如果加油站刚好在起点，更新起点的初始油价
        if di <= 0:
            m = min(m, pi)
        # 忽略超越终点的加油站
        elif di < d1:
            raw_stations.append((di, pi))

    # 按距离从小到大排序
    raw_stations.sort(key=lambda x: x[0])

    # 构建完整的站点列表：起点 + 中途加油站 + 终点
    # 终点油价设为 0，确保它比任何加油站都便宜
    stations = [(0.0, m)] + raw_stations + [(d1, 0.0)]

    max_range = c * d2  # 满油状态下的最大行驶距离
    num_stations = len(stations)

    # 检查是否可达
    for i in range(num_stations - 1):
        if stations[i+1][0] - stations[i][0] > max_range:
            print("No Solution")
            return

    total_cost = 0.0
    current_fuel = 0.0
    i = 0

    while i < num_stations - 1:
        # 在最大行驶范围内，寻找第一个比当前站点油价更便宜的站点
        next_cheaper_idx = -1
        for j in range(i + 1, num_stations):
            if stations[j][0] - stations[i][0] > max_range:
                break
            if stations[j][1] < stations[i][1]:
                next_cheaper_idx = j
                break

        if next_cheaper_idx != -1:
            # 情况 1：找到了更便宜的站点
            dist_to_next = stations[next_cheaper_idx][0] - stations[i][0]
            req_fuel = dist_to_next / d2
            if current_fuel < req_fuel:
                buy_fuel = req_fuel - current_fuel
                total_cost += buy_fuel * stations[i][1]
                current_fuel = req_fuel
            current_fuel -= req_fuel
            i = next_cheaper_idx
        else:
            # 情况 2：范围内没有更便宜的站点，加满油前往下一站
            buy_fuel = c - current_fuel
            total_cost += buy_fuel * stations[i][1]
            current_fuel = c

            dist_to_next = stations[i+1][0] - stations[i][0]
            used_fuel = dist_to_next / d2
            current_fuel -= used_fuel
            i += 1

    print(f"{total_cost:.2f}")

if __name__ == '__main__':
    solve()