Solution of P9749
SJZ2010
·
·
题解
做法
可以考虑贪心。
首先我们发现在 1 号加油站必须买油，否则根本动不了。接下来我们可以不断开到在当前加油站后比当前加油站油价低的加油站并使油剩得最少。
什么意思？拿样例来说，就是这样：
样例：
5 4
10 10 10 10
9 8 9 6 5
为什么呢？
假如我们现在有一排加油站，第 $i$ 个加油站的油价是 $oil_i$，$i$ 站到 $i+1$ 站的距离是 $dis_i$。我们先处理出 $1$ 号加油站到 $i$ 号加油站的总距离 $sum_i$。
假如我们现在在 $a$ 号加油站，要去 $b$ 号加油站，中间有个 $c$ 号加油站且 $oil_c < oil_a$。
按照我们的策略，我们一定要去 $c$，这样花了 $\lceil\frac{sum_c-sum_a}{d}\rceil \times oil_a + \lceil\frac{sum_b-sum_c}{d}\rceil \times oil_c$ 块钱。
不去 $c$ 的话，价格就是 $\lceil\frac{sum_b-sum_a}{d}\rceil \times oil_a$。
其实去 $c$ 的式子少考虑了从 $a$ 到 $c$ 后车里还有油，所以消耗的总油量其实就是 $\lceil\frac{sum_b-sum_a}{d}\rceil$。由于 $oil_c < oil_a$，所以去 $c$ 价格是更低的。
## 代码
注意要算一下开到某站还剩下多少油。
以及**不开 `long long` 见祖宗**。
```cpp
#include <cstdio>
typedef long long ll;
const int N = 1e5 + 5;
ll n, d;
ll dis[N], money[N], nxt[N], dis_sum[N], can_dis, ans;
int main()
{
//freopen("road.in", "r", stdin);
//freopen("road.out", "w", stdout);
scanf("%lld %lld", &n, &d);
ll i, dist, last_m, last_i;
for (i = 1; i < n; i++)
scanf("%lld", &dis[i]);
for (i = 2; i <= n; i++)
dis_sum[i] = dis_sum[i - 1] + dis[i - 1];// 计算从 1 到 i 的距离
for (i = 1; i <= n; i++)
scanf("%lld", &money[i]);
last_m = money[1];
last_i = 1;
for (i = 2; i <= n - 1; i++)
{
if (money[i] < last_m)// 遇到比上一个加油站便宜的
{
nxt[last_i] = i;// 类似与链表的方式存储下一个加油站
last_i = i;
last_m = money[i];
}
}
nxt[last_i] = n; // 要到 n 号点，可以把 n 号点看作价钱位 0
for (i = 1; i < n;)
{
dist = dis_sum[nxt[i]] - dis_sum[i];
ans += (dist - can_dis + d - 1) / d * money[i];// 要考虑还剩多少油
// can_dis 表示还能开多少距离
can_dis += (dist - can_dis + d - 1) / d * d; // 注意油量要向上取整
can_dis -= dist;
i = nxt[i];// 向下一个加油站开
}
printf("%lld\n", ans);
return 0;
}
```