【题目描述】

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

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

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

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

【输入描述】

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

输入的第二行包含n-1个正整数v1，v2,v3...Vn-1分别表示站点间的距离。

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

【输出描述】

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

【样例输入】

5 4
10 10 10 10
9 8 9 6 5

【样例输出】

79

【提示】

【样例 1 解释】

【数据范围】

对于所有测试数据保证：$1\le n\le {10}^5$ ，1$$≤d≤10^5 ，1$$≤vi≤10^5 ，1$$≤ai≤10^5 。

【题目分析】

过程图解参考如下：

（1）首先，1号油站必须买油，否则动不了。

（2）考虑贪心策略，一开始所有的数据都是已知的，如果我们到到达n点发现没有油了，应该从n点（假设是3点）以前的加油站中挑选一个价格最低且能到达下一个加油站

（3）数据量比较大，要开long long。

（4）注意油箱足够大，可以装无限多的油。

（5）没有必要在最后一个站点n加油，因为我们的目的就是到n。

【参考答案】

#include <bits/stdc++.h>
using namespace std;
int v[100005], price[100005]; //距离和价格 
int n, d; //n个站点，d表示每升油可以前进的距离 
long long ans = 0, s = 0; //ans表示总费用，s表示 站点和站点之间的距离和 
int main() {
    scanf("%d%d", &n, &d);
    for (int i = 1; i < n; i++){
    	scanf("%d", &v[i]);   //n-1个站点之间的距离 
	} 
    int minn = INT_MAX; //最小值 
    for (int i = 1; i < n; i++) {
        scanf("%d", &price[i]); //读入价格 
        s += v[i]; //累计站点和站点之间的距离和 
        minn = min(minn, price[i]);  //找到到当前站点的最低油价 
        //距离小于0说明上次加的油可以走的更远，就是还有油 
		if (s > 0) {
        	// 总价钱=距离*油价
			int distance =  (s + d - 1) / d ; //到目前为止的距离(走了一站) 
            ans += distance* minn;  //累计价钱 
            s -= distance* d; // 往前走， 
        }
    }
    printf("%lld\n", ans);
    return 0;
}

【参考答案2】

#include <bits/stdc++.h>
using namespace std;
long long n,d,sum,a[100010],v[100010],mi[100010];
signed main() {
	cin>>n>>d;
	for(int i=1; i<n; i++) {
		cin>>v[i];
		v[i]=v[i-1]+v[i];//把距离做叠加起来，距离和 
	}
	for(int i=1; i<=n; i++)
		cin>>a[i]; //价格 
	mi[1]=a[1]; //第一个点必须加油 
	for(int i=2; i<=n; i++) 
		mi[i]=min(mi[i-1],a[i]); //维护前缀最小值
	int now=0;//now保存的是当前距离起点多少距离
	for(int i=1; i<n; i++) {
		if(now>v[i]) 
			continue;//如果超过了i+1的距离，那么就不用考虑当前加油站买油，直接考虑下一个加油站
		int k=ceil((v[i]-now)*1.0/d*1.0);//买的最少升数
		sum+=k*mi[i];//钱
		now+=k*d;//距离
	}
	cout<<sum;
	return 0;
}