求从景点1开车到景点 n，至少要花费多少钱加油

Question

【问题描述】

在一条笔直道路上开车旅行，沿路有许多景点。

将道路视为一条数轴，道路上有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买了3升油，在景点2购买了5升油，在景点4购买了2升油。

【数据要求】

1 <= n,d,vi,ai <= 1000

C
(current)

草稿箱
1
​
控制台

Answer 1

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000

int n, d, v[MAX_N], a[MAX_N];

// 计算从景点i到景点j需要加多少油
int get_fuel(int i, int j) {
    int len = v[j-1] - v[i-1];
    return (len + d - 1) / d;
}

int main() {
    scanf("%d %d", &n, &d);
    for (int i = 1; i < n; i++) {
        scanf("%d", &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    int cur_pos = 1, fuel_left = 0, total_cost = 0;
    while (cur_pos < n) {
        int min_cost = -1, min_pos = -1, max_fuel = 0;
        // 找到所有能够到达的加油站中成本最小的一个
        for (int i = cur_pos+1; i <= n && v[i-1] - v[cur_pos-1] <= d*fuel_left; i++) {
            int fuel_needed = get_fuel(cur_pos, i);
            if (fuel_needed > max_fuel) {
                max_fuel = fuel_needed;
                min_cost = a[i];
                min_pos = i;
            } else if (fuel_needed == max_fuel && a[i] < min_cost) {
                min_cost = a[i];
                min_pos = i;
            }
        }

        // 如果没有能够到达的加油站，就加满油
        if (min_pos == -1) {
            fuel_left = d;
            total_cost += a[cur_pos] * fuel_left;
        } else {
            int fuel_needed = get_fuel(cur_pos, min_pos);
            total_cost += a[cur_pos] * (fuel_needed - fuel_left);
            fuel_left = fuel_needed - (v[min_pos-1] - v[cur_pos-1]) / d;
            cur_pos = min_pos;
        }
    }

    printf("%d\n", total_cost);
    return 0;
}