2099：【23CSPJ普及组】公路(road)时间限制: 1000 ms 内存限制: 524288 KB 提交数:3793 通过数: 1575 【题目描述】小苞准备开着车沿着公路自驾。 公路上一共有 nn 个站点，编号为从 11 到nn。其中站点 ii 与站点i+1i+1 的距离为vivi 公里。 公路上每个站点都可以加油，编号为ii 的站点一升油的价格为aiai 元，且每个站点只出售整数升的油。 小苞想从站点 11 开车到站点 nn，一开始小苞在站点 11 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进dd 公里。问小苞从站点 11 开到站点 nn，至少要花多少钱加油？ 【输入】输入的第一行包含两个正整数 nn 和dd，分别表示公路上站点的数量和车每升油可以前进的距离。 输入的第二行包含n−1n−1 个正整数v1v1,v2v2…vn−1vn−1 ，分别表示站点间的距离。 输入的第三行包含 nn 个正整数 a1a1,a2a2…anan ，分别表示在不同站点加油的价格。 【输出】输出一行，仅包含一个正整数，表示从站点 11 开到站点 nn，小苞至少要花多少钱加油。 【输入样例】【输出样例】【提示】【样例 1 解释】 最优方案下：小苞在站点 11 买了 33 升油，在站点22 购买了 55 升油，在站点 44 购买了 22 升油。 【数据范围】 对于所有测试数据保证：1≤n≤1051≤n≤105 ，1≤d≤1051≤d≤105 ，1≤vi≤1051≤vi≤105 ，1≤ai≤1051≤ai≤105 。
特殊性质 A：站点 11 的油价最低。 特殊性质 B：对于所有1≤i<n1≤i<n，vivi为 dd 的倍数。 |
#include <bits/stdc++.h>
using namespace std;
long long v[100001], a[100001]; //v为站点距离 a为不同站点的加油价格
int main()
{long long n,d;double oil=0,leave=0;//leave 表示目前还剩多少升油 long long money=0;cin>>n>>d;for(int i=1;i<=n-1;i++)cin>>v[i];for(int i=1;i<=n;i++)cin>>a[i];int i=1;while(i<=n) //站点 {int j=i+1;for(;j<=n-1;j++) //贪心算法，加油加到到比目前站点小的价格 if(a[i]>a[j])break;double dis=0;for(int k=i+1;k<=j;k++) //加油的距离即为i站点到j点的距离dis+=v[k-1]; //注意距离即为前站点i-1的距离 oil=dis/d-leave; double buy=ceil(oil);leave=buy-oil;money+=buy*a[i];i=i!=j?j:i++; //不能用for,否则i=j后，i会继续加1 }cout<<money; return 0;
}
