公路（road）
【题目描述】
小苞准备开着车沿着公路自驾。
公路上一共有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买了3升油，在站点2购买了 5升油，在站点 4购买了2升油。
【数据范围】
对于所有测试数据保证： ，1
【题目分析】
过程图解参考如下：
（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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。