【题目描述】

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

公路上一共有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;  }

(adsbygoogle = window.adsbygoogle || []).push({});