本文主要是介绍5308. 公路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
有n 个站点，站点可以加油，站点之间的油的价格不一定相等，站点的编号从1到n，站点之间的距离用v表示，站点的油价用a表示，求从1站点到n站点所需要的最小的油价是多少
数据范围
对于所有测试数据保证：1≤n≤105
，1≤d≤105
，1≤vi≤105
，1≤ai≤105
输入
依次输入站点数目n，每一升油可以跑的距离，站点之间的距离，站点的油的价格
5 4
10 10 10 10
9 8 9 6 5
输出
79
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long v[N],a[N],o[N];
int main()
{int n,d;cin>>n>>d;for(int i=2;i<=n;i++){cin>>v[i];v[i]+=v[i-1];o[i]=ceil((double)v[i]/d);}for(int i=1;i<=n;i++) cin>>a[i];long long p=a[1];long long ans=0;for(int i=1;i<=n;i++){ans+=p*(o[i]-o[i-1]);p=min(p,a[i]);}cout<<ans<<endl;return 0;
}
想法
前缀和＋维护最小值
o数组表示的是油的升数，p表示的是最小的油价，ans表示总的花费
贪心的思想，每一次都是使用当前最小的油价
好像代码很短，非常简单，以上，准备等y总直播讲解完这题，再对该博客进行一些补充和修改
向上取整是防止跑到一半没有油了，宁可多出一点也不可以半路熄火
这篇关于5308. 公路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
