周口网站推广,dedecms 安防监控行业网站模板,黄冈网站建设设计,开发小程序怎么赚钱【题目来源】https://www.luogu.com.cn/problem/P9749https://www.acwing.com/problem/content/5311/【题目描述】 小苞准备开着车沿着公路自驾。 公路上一共有 n 个站点#xff0c;编号为从 1 到 n。 其中站点 i 与站点 i1 的距离为 vi 公里。 公路上每个站点都可以加油…【题目来源】https://www.luogu.com.cn/problem/P9749https://www.acwing.com/problem/content/5311/【题目描述】 小苞准备开着车沿着公路自驾。 公路上一共有 n 个站点编号为从 1 到 n。 其中站点 i 与站点 i1 的距离为 vi 公里。 公路上每个站点都可以加油编号为 i 的站点一升油的价格为 ai 元且每个站点只出售整数升的油。 小苞想从站点 1 开车到站点 n一开始小苞在站点 1 且车的油箱是空的。 已知车的油箱足够大可以装下任意多的油且每升油可以让车前进 d 公里。 问小苞从站点 1 开到站点 n至少要花多少钱加油【输入格式】 输入的第一行包含两个正整数 n 和 d 分别表示公路上站点的数量和车每升油可以前进的距离。 输入的第二行包含 n−1 个正整数 v1,v2,…,vn−1分别表示站点间的距离。 输入的第三行包含 n 个正整数 a1,a2…an分别表示在不同站点加油的价格。【输出格式】 输出一行仅包含一个正整数表示从站点 1 开到站点 n小苞至少要花多少钱加油。【数据范围】 对于所有测试数据保证1≤n≤10^51≤d≤10^51≤vi≤10^51≤ai≤10^5。
测试点n≤特殊性质1∼58无6∼1010^3无11∼1310^5A14∼1610^5B17∼2010^5无
特殊性质 A站点 1 的油价最低。 特殊性质 B对于所有 1≤invi 为 d 的倍数。【输入样例】 5 4 10 10 10 10 9 8 9 6 5【输出样例】 79【样例解释】 最优方案下小苞在站点 1 买了 3 升油在站点 2 购买了 5 升油在站点 4 购买了 2 升油。 【算法分析】 很明显的贪心问题如果第 i 站点的油价较 i1 的贵i 站的油只要负责到 i1 站 否则 i 站的油要多加直到遇到比他便宜的站。【算法代码】
#include bits/stdc.h
using namespace std;const int maxn1e55;
long long v[maxn];
long long a[maxn];
long long fc[maxn];int n,d;
long long ans;
long long price;main() {cinnd;for(int i2; in; i) {cinv[i];v[i]v[i-1]; //Distance from site i to the starting pointfc[i]ceil(1.0*v[i]/d); //Fuel consumption from starting point to current site}for(int i1; in; i) cina[i];pricea[1];for(int i2; in; i) {ansprice*(fc[i]-fc[i-1]);pricemin(price,a[i]);}coutans;return 0;
}/*
in:
5 4
10 10 10 10
9 8 9 6 5out:
79
*/
【参考文献】https://www.acwing.com/solution/content/206442/https://mp.weixin.qq.com/s/zckJsihxsDT2JNBFK1ipxAhttps://www.acwing.com/solution/content/220349/
