NOI-CSP/J 2023 T1：公路问题 [P9749]

题目描述

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

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

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

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

输入格式

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

输入的第二行包含 n−1 个正整数 v1​,v2​…vn−1​，分别表示站点间的距离。

输入的第三行包含 n 个正整数 a1​,a2​…an​，分别表示在不同站点加油的价格。

输出格式

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

输入输出样例

**输入

5 4 10 10 10 10 9 8 9 6 5

**输出

79

说明/提示

【样例 1 解释】

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

【样例 2】

见选手目录下的 road/road2.in 与 road/road2.ans。

【数据范围】

对于所有测试数据保证：1≤n≤105，1≤d≤105，1≤vi​≤105，1≤ai​≤105。

• 特殊性质 A：站点 1 的油价最低。

• 特殊性质 B：对于所有 1≤i<n，vi​ 为 d 的倍数。

#include <iostream>
#include <fstream>

using namespace std;

int main() {

    typedef long long ll; // 定义长整型别名，方便处理大数

    ifstream fin("road2.in"); // 输入文件流，用于读取输入数据
    ofstream fout("road2.out"); // 输出文件流，用于写入输出数据

    int n, d; // n为站点数，d为每单位油料能行驶的距离
    fin >> n >> d; // 从文件中读取n和d
    ll distances[n - 1]; // 使用原生数组存储每段距离
    ll prices[n]; // 使用原生数组存储每个站点油价

    // for (int i = 0; i < n - 1; ++i) {
    //     fin >> distances[i]; // 读取每段距离
    // }    
    // for (int i = 0; i < n; ++i) {
    //     fin >> prices[i]; // 读取每个站点的油价
    // }
    for (ll& distance : distances) 
        fin >> distance; // 读取每段距离
    for (ll& price : prices) 
        fin >> price; // 读取每个站点的油价

    ll totalCost = 0; // 总花费初始化为0
    ll lowestPrice = prices[0]; // 当前油价初始化为第一个站点的油价
    ll restDistance = 0; // 剩余可行驶距离初始化为0

    for (int i = 0; i < n - 1; ++i) {
        cout << "#" << i << endl;
        cout << "Distance:\t" << distances[i] << " - " << restDistance << " = " << (distances[i] - restDistance) << endl; // 输出当前段所需行驶距离到控制台
        cout << "Lowest Price:\t" << lowestPrice << "\tNow/Next Price: " << prices[i] << "/" << prices[i + 1] << endl; // 输出当前油价到控制台
        ll distance = distances[i] - restDistance; // 计算当前段所需行驶距离，考虑剩余可行驶距离
        ll fuel = (distance + d - 1) / d; // 计算需要购买的油料量，向上取整
        ll cost = fuel * lowestPrice;
        cout << "Cost:\t\t" << fuel << " * " << lowestPrice << " = " << cost << endl; // 输出当前段油料花费到控制台
        cout << "Total Cost:\t" << totalCost << " + " << cost << " = " << totalCost + cost << endl; // 输出总花费到控制台
        totalCost += cost; // 累加当前段的油料花费
        restDistance = fuel * d - distance; // 更新剩余可行驶距离
        cout << "Rest Distance:\t" << restDistance << endl; // 输出剩余可行驶距离到控制台
        cout << "-----------------------------" << endl; // 输出分隔线到控制台

        // 如果下一站的油价更低，更新当前油价
        //lowestPrice = min(lowestPrice, prices[i + 1]);
        if( lowestPrice > prices[i + 1])
        {
            lowestPrice = prices[i + 1];
            cout << "*** [" << i << "] Lowest Price Updated to: " << lowestPrice << endl;
        }
    }

    cout << totalCost << endl; // 输出总花费到控制台
    cout.flush(); // 刷新输出缓冲区
    fout << totalCost << endl; // 输出总花费到文件

    fin.close(); // 关闭输入文件流
    fout.close(); // 关闭输出文件流

    return 0; // 返回0表示程序正常结束
}