CSP-J 2023 公路 题解

还有1天就刑满释放了来发个题解

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

int n, d;
long long v[114154], sum[114514], a[114514];
//v[i]表示距离 sum[i]表示1~i的距离总和 a[i]表示油价
long long cur, ans;
//cur表示当前已经走了多长的距离，ans表示花了多少钱

int main () {
    freopen ("road.in", "r", stdin);
    freopen ("road.out", "w", stdout);

    cin >> n >> d;
    for (int i = 1; i < n; i++){//注意n个点只有n - 1条边，所以是i < n
        cin >> v[i];//加油站i到加油站i+1的距离
        sum[i] = sum[i-1] + v[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> a[i];//加油站i的油价
        if (i>1) {
            a[i] = min(a[i], a[i-1]);
        }
    }
    for(int i = 1; i < n; i++){
        int temp = max((long long)0, sum[i] - cur);
        //从cur出发到加油站i+1的距离
        int oil = (temp+d-1) / d;
        //走temp的距离需要消耗多少油(向上取整)
        cur += oil*d;//统计总路程
        ans += oil*a[i];//统计总花费
    }
    cout << ans;//见证奇迹的时刻

    fclose (stdin);
    fclose (stdout);
}