【CSP】CSP-J 2023真题 | 公路 luogu-P9749 (适合GESP四级及以上考生练习)

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

P9749 [CSP-J 2023] 公路

题目要求

题目描述

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

公路上一共有  个站点，编号为从  到 。其中站点  与站点  的距离为  公里。

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

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

输入格式

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

输入的第二行包含  个正整数 ，分别表示站点间的距离。

输入的第三行包含  个正整数 ，分别表示在不同站点加油的价格。

输出格式

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

输入输出样例 #1

输入 #1

5 410 10 10 109 8 9 6 5

输出 #1

79

说明/提示

【样例 1 解释】

最优方案下：小苞在站点  买了  升油，在站点  购买了  升油，在站点  购买了  升油。

【数据范围与约定】

对于所有测试数据保证：，，，。

• 特殊性质 A：站点  的油价最低。
• 特殊性质 B：对于所有 ， 为  的倍数。

题目分析

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

1. 贪心策略

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

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

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

2. 模拟步骤

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

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

3. 数据范围与数据类型

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

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

示例代码

#include<iostream>#include<vector>#include<algorithm>intmain(){    // 优化输入输出流性能    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<longlong> v(n);    for (int i = 1; i < n; ++i) {        std::cin >> v[i];    }    // a[i] 表示第 i 个站点的油价    std::vector<longlong> 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 避免溢出，是解决此类模拟和贪心问题需要注意的细节。