【QED】HHG的旅途

本文主要是介绍【QED】HHG的旅途，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

HHG想通过自驾车的方式从自己的城市去另一个城市旅游，并尽量让自己玩得开心。已知：

① 两个城市之间有 $n$（$1\le n\le 10^5$）个加油站

② 第 $i$ 个加油站的油费为 $a_i$ / 每升（$1\le a_i\le 10^5$）

③ 第 $i$ 个和第 $i+1$ 个加油站之间的距离为 $d_i$（$1\le d_i\le 10^5$）

④ 汽车的行驶速度为 $v$ / 每升($1\le v\le 10^5$)

由于HHG给油箱施了魔法，使得油箱的容量无限大，所以根本不用担心油是否为溢出。为了在另一个城市旅游玩的开心，你需要求HHG在自驾过程中最小的花费。起初，油箱的初始值为 $0$，HHG的预算为 $m$ 元 ($1\le m\le 10^9$)。由于HHG考虑周全，它把全部的行程都安排好了，即出发$\to$游玩$\to$返程，游玩的费用为 $c$ 元 ($1\le c\le 10^9$)。

HHG的预算能否完成一次完整的旅途（即剩余的钱不为负数）？如果可以完成则输出最小的花费，否则输出“Failed journey!”（不含双引号）。

输入格式

第一行，输入四个以空格分隔的整数 $n,m,c,v$，分别代表加油站的个数，预算金额，游玩费用，以及汽车行车速度。

第二行，输入 $n$ 个整数，以空格分隔，其中第 $i$ 个数表示加油站的油费价格 $a_i$。

第三行，输入 $n–1$ 个整数，以空格分隔，其中第 $i$ 个数表示相邻两个（即第 $i$ 个和第 $i+1$ 个）加油站之间的距离 $d_i$。

输出格式

输出所需最小的花费，答案四舍五入保留两位小数，如果不能完成往返旅途，则输出“Failed journey!”。

测试样例

3 15 4 6
4 2 3
12 6

Failed journey!

3 30 4 6
4 4 4
6 12

28.00

数据范围汇总

$1\le n,v,a_i,d_i\le 10^5$

$1\le m,c\le 10^9$

思路

这道题目我们可以使用贪心的思想，前往目的地的过程中我们要想花费的费用最少肯定会优先查找油价最小的加油站加多一点油，并且找到最小的价格时候我们就不再加油了，那问题就转变成如何花费最找费用前往（前往目的地的过程中油价最低的）加油站，以此类推，换句话来说就是每次加油我们加到刚刚好能到下一个油价更低的加油站。

核心代码

#include <iostream>
using namespace std;int w[100010], s[100010];int main() {int n, m, c, v;scanf("%d%d%d%d", &n, &m, &c, &v);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);for (int i = 2; i <= n; i++) {scanf("%d", &s[i]);s[i] += s[i-1];}s[n+1] = s[n];double ans = c;int minzhi = w[1];for (int i = 1, j = 1; i <= n; ) {while (j <= n && w[j] >= w[i]) j++;if (n>=j) minzhi = min(minzhi, w[j]);ans += 1.0 * w[i] * (s[j] - s[i]) / v;i = j;} ans += 1.0 * s[n] / v * minzhi;if (ans <= m) printf("%.2lf\n", ans);else printf("Failed journey!\n");return 0;
}

这篇关于【QED】HHG的旅途的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---