P9749 [CSP-J 2023] 公路 题解与代码详解

一、题目核心思想

这道题是一道经典的贪心算法入门题，最优解完全基于一个极其简单的贪心策略，也就是你说的：

永远用目前见过的最便宜的油来跑每一段路。

我们从起点出发，每到达一个加油站，先更新我们目前见过的最低油价。然后开往下一个加油站时，如果车里还有油就先用剩余的；如果不够，就按照目前见过的最低油价来买油，不管我们现在在哪个加油站。

因为题目中明确说明油箱无限大，所以我们可以在任何时候买油，然后在任何时候用。油的价格是固定的，什么时候用不影响总花费。这个策略是100%正确的，而且是所有解法中最简单、最优雅的一个。

二、贪心策略通俗解释

你可以把这个过程想象成：

1. 你开车上路，随身带一个小本子，专门记录你见过的最便宜的油价
2. 每到一个新的加油站，先看看这个加油站的油价比你本子上记的便宜吗？如果便宜，就更新本子上的价格
3. 然后你要开往下一个地方，看看车里的油够不够
4. 如果够，直接开过去就行
5. 如果不够，你就按照本子上记的那个最便宜的价格来买油，买够能开到下一个地方的量
6. 重复这个过程，直到到达终点

三、为什么这个策略一定是最优的？

反证法：假设存在一段路程，你用了价格为x的油来跑，但其实你之前可以买到价格为y的油，且y < x。那么，你把这部分油换成y元的油，总花费就会减少，这与"最优解"矛盾。

所以，每一段路程都用目前为止最便宜的油来跑，一定能得到全局最优解。

四、带完整注释的代码

#include<bits/stdc++.h>
using namespace std;

// 题目中n最大为1e5，数组开1e5+10防止越界
const int MAXN = 1e5 + 10;

int main(){
    // 加速cin输入，对于1e5的数据量必须加，否则可能超时
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // n: 站点总数
    // d: 每升油可以让车前进的公里数
    int n,d;
    cin >> n >> d;
    
    // v[i]: 站点i到站点i+1之间的距离（公里）
    // 注意：只有n-1段路，所以i从1到n-1
    int v[MAXN];
    for(int i=1; i<n; i++){
        cin >> v[i];
    }
    
    // a[i]: 站点i的油价（元/升）
    // 注意：有n个站点，所以i从1到n
    int a[MAXN];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    
    // ans: 总花费，必须用long long！
    // 最大可能花费：1e5段路 × 1e5公里/段 ÷ 1公里/升 × 1e5元/升 = 1e15
    // 远远超过int的范围（约2e9）
    long long ans = 0;
    
    // m: 目前为止见过的最低油价，初始化为第一个站点的油价
    int m = a[1];
    
    // res: 当前油箱里的油还能行驶的公里数，初始化为0（一开始油箱是空的）
    int res = 0;
    
    // 逐段处理每一段路，从站点1到站点n，共n-1段路
    for(int i=1; i<n; i++){
        // 第一步：到达站点i，更新目前见过的最低油价
        // 这就是你说的："先记录到最便宜的油价"
        m = min(m, a[i]);
        
        // 第二步：准备开往下一个站点i+1，路程是v[i]公里
        if(res >= v[i]){
            // 情况1：剩余的油够跑这段路，直接用剩余的油
            res -= v[i];
        } else {
            // 情况2：剩余的油不够跑这段路，需要加油
            // need: 还需要行驶多少公里才能跑完这段路
            int need = v[i] - res;
            
            // t: 需要加多少升油
            // 因为只能买整数升油，所以需要向上取整
            // 公式：(a + b - 1) / b 是正整数a除以正整数b向上取整的通用写法
            int t = (need + d - 1) / d;
            
            // 按照目前见过的最低油价m购买t升油，加到总花费
            // 这里强制转换m为long long，防止m*t溢出int范围
            ans += (long long)m * t;
            
            // 加完油后，计算新的剩余可行驶公里数
            // 加了t升油，能跑t*d公里，加上原来剩余的res公里，减去跑这段路用掉的v[i]公里
            res = t * d + res - v[i];
        }
    }
    
    // 输出总花费
    cout << ans << endl;
    
    return 0;
}

五、样例1模拟运行

我们用题目中的样例1来一步步验证这个思路和代码的正确性：

样例1输入

5 4
10 10 10 10
9 8 9 6 5

运行过程

最终输出79，和样例完全一致！

六、代码优势说明

这个实现方式比传统的"用单调栈找下一个更小元素"的方法有三个巨大的优势：

1. 逻辑更简单：不需要理解复杂的单调栈概念，只需要记住"永远用最便宜的油"
2. 代码更短：只有一次遍历，没有任何预处理
3. 更不容易出错：没有复杂的边界条件，考试中写得快、正确率高

七、考试注意事项

1. 必须用long long存总花费：这是这道题最容易丢分的地方
2. 必须加输入加速：对于1e5的数据量，不加ios::sync_with_stdio(false)可能会超时
3. 向上取整公式要记牢：(a + b - 1) / b只适用于正整数
4. 强制类型转换：计算m*t时要把其中一个数转成long long，防止溢出