2023真题 | 公路 luogu-P9749

CSP-J 2023真题“公路”是一道典型的贪心算法题。本题要求计算出在不同站点油价不同的情况下，从起点行驶到终点的最小花费。适合 GESP 四级及以上考生练习，难度⭐⭐，洛谷难度等级普及-。

P9749 [CSP-J 2023] 公路

题目要求

题目描述

小苞准备开着车沿着公路自驾。

公路上一共有 $n$ 个站点，编号为从 $1$ 到 $n$。其中站点 $i$ 与站点 $i + 1$ 的距离为 $v_i$ 公里。

公路上每个站点都可以加油，编号为 $i$ 的站点一升油的价格为 $a_i$ 元，且每个站点只出售整数升的油。

小苞想从站点 $1$ 开车到站点 $n$，一开始小苞在站点 $1$ 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 $d$ 公里。问小苞从站点 $1$ 开到站点 $n$，至少要花多少钱加油？

输入格式

输入的第一行包含两个正整数 $n$ 和 $d$，分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 $n - 1$ 个正整数 $v_1, v_2\dots v_{n-1}$，分别表示站点间的距离。

输入的第三行包含 $n$ 个正整数 $a_1, a_2 \dots a_n$，分别表示在不同站点加油的价格。

输出格式

输出一行，仅包含一个正整数，表示从站点 $1$ 开到站点 $n$，小苞至少要花多少钱加油。

输入输出样例 #1

输入 #1

5 4
10 10 10 10
9 8 9 6 5

输出 #1

79

说明/提示

【样例 1 解释】

最优方案下：小苞在站点 $1$ 买了 $3$ 升油，在站点 $2$ 购买了 $5$ 升油，在站点 $4$ 购买了 $2$ 升油。

【数据范围与约定】

对于所有测试数据保证：$1 \leq n \leq 10^5$，$1 \leq d \leq 10^5$，$1 \leq v_i \leq 10^5$，$1 \leq a_i \leq 10^5$。

• 特殊性质 A：站点 $1$ 的油价最低。
• 特殊性质 B：对于所有 $1 \leq i < n$，$v_i$ 为 $d$ 的倍数。

题目分析

本题要求计算从小苞的起点（站点 $1$）行驶到终点（站点 $n$）的最低花费。因为油箱的容量是无限的，这是一道经典的贪心算法题。

1. 贪心策略

由于可以在前面的任何一个站点提前购买后续所需的油，因此在任意位置，我们都应该选择在已访问过的站点中，油价最低的那个进行加油。

也就是说，我们在模拟行驶的过程中：

• 始终维护一个变量 cur_min_price，表示从起点到当前站点所经过的最低油价。
• 当到达一个新站点时，若它的油价更低，我们就更新 cur_min_price。
• 如果当前油箱里的油不够支撑我们走到下一个站点，我们就在当前已知的最低油价站点购买刚好足够的油（由于只能买整数升，可能会有多余的油留到后续站点使用）。

2. 模拟步骤

我们可以从站点 $1$ 开始，模拟向终点行驶：

1. 记录已访问过的最低油价 cur_min_price。初始时 cur_min_price = a[1]。
2. 记录油箱中剩余油量能支撑行驶的距离 leftover_dist。初始时 leftover_dist = 0。
3. 从 $i = 1$ 到 $n - 1$ 依次遍历每一个站点：
   • 比较当前剩余可行驶距离 leftover_dist 与站点 $i$ 到 $i+1$ 的距离 $v_i$。
   • 若 leftover_dist < v_i，说明需要补充油量。所需补充的距离为 needed_dist = v_i - leftover_dist。
   • 需要购买的整数升油量为： $\text{liters} = \lceil \text{needed\_dist} / d \rceil = \lfloor (\text{needed\_dist} + d - 1) / d \rfloor$
   • 累加花费：ans += liters * cur_min_price。
   • 更新剩余可行驶距离：leftover_dist += liters * d。
   • 扣除本次行驶消耗的距离：leftover_dist -= v_i。
   • 到达下一个站点 $i+1$ 后，更新最低油价：cur_min_price = min(cur_min_price, a[i+1])。

3. 数据范围与数据类型

• 站点数 $n \le 10^5$，站点间距离 $v_i \le 10^5$，因此总距离可能达到 $10^{10}$。
• 油价 $a_i \le 10^5$，最大花费可能达到 $10^{15}$。
• C++ 中标准的 int 类型上限约为 $2 \times 10^9$。因此，表示距离、剩余可行驶距离以及总花费的变量必须使用 long long 类型，否则会导致数值溢出而计算错误。

时间复杂度：由于只需对站点进行一次单向遍历，算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，可以高效通过全部测试点。

示例代码

以下是使用 C++ 实现的代码：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 优化输入输出流性能
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    long long d;
    std::cin >> n >> d;

    // v[i] 表示第 i 个站点与第 i + 1 个站点之间的距离
    std::vector<long long> v(n);
    for (int i = 1; i < n; ++i) {
        std::cin >> v[i];
    }

    // a[i] 表示第 i 个站点的油价
    std::vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    long long ans = 0;             // 累计总花费
    long long leftover_dist = 0;   // 剩余油量可行驶的距离
    long long cur_min_price = a[1]; // 当前遇到的最低油价

    for (int i = 1; i < n; ++i) {
        // 如果剩余的油不够行驶到下一个站点，则在最低价站点加油
        if (leftover_dist < v[i]) {
            long long needed_dist = v[i] - leftover_dist;
            // 计算需要购买的整升油量（向上取整）
            long long liters = (needed_dist + d - 1) / d;
            ans += liters * cur_min_price;
            leftover_dist += liters * d;
        }
        // 减去走到下一个站点消耗的距离
        leftover_dist -= v[i];
        // 更新到达下一个站点后的最低油价
        cur_min_price = std::min(cur_min_price, a[i + 1]);
    }

    std::cout << ans << "\n";

    return 0;
}

结语

本题的关键在于利用“油箱容量无限”这一特点，将分段购买的问题转化为“在已知的最低价站点提前购买”的贪心决策。在编写代码时，合理分析物理量可能达到的最大值并使用 long long 避免溢出，是解决此类模拟和贪心问题需要注意的细节。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号