TZOJ:8404: 公路

标签:贪心

描述

小苞准备开着车沿着公路自驾。

公路上一共有 n?个站点，编号为从 1?到 n。其中站点 i?与站点 i+1?的距离为 vi?公里。

公路上每个站点都可以加油，编号为 i?的站点一升油的价格为 ai?元，且每个站点只出售整数升的油。

小苞想从站点?1 开车到站点 n，一开始小苞在站点 1?且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 d?公里。问小苞从站点?1 开到站点 n，至少要花多少钱加油？

输入

输入的第一行包含两个正整数 n?和 d，分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 n?1?个正整数 v1,v2…vn?1，分别表示站点间的距离。

输入的第三行包含 n?个正整数 a1,a2…an，分别表示在不同站点加油的价格。

输出

输出一行，仅包含一个正整数，表示从站点?1 开到站点 n，小苞至少要花多少钱加油。

样例输入

5 4
10 10 10 10
9 8 9 6 5

样例输出

79

提示

【样例 1 解释】

最优方案下：小苞在站点 1?买了 3?升油，在站点?2 购买了 5?升油，在站点 4?购买了 2?升油。

【数据范围】

对于所有测试数据保证：1≤n≤105，1≤d≤105，1≤vi≤105，1≤ai≤105。

测试点	n≤	特殊性质
1～51～5	88	无
6～106～10	103103	无
11～1311～13	105105	A
14～1614～16	105105	B
17～2017～20	105105	无

特殊性质 A：站点 1?的油价最低。

特殊性质 B：对于所有 1≤i<n，vi?为 d?的倍数。

/* 贪心问题 */
/* 千万要注意范围,int太小了,过不了 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;   // long long避免超出范围
const int N = 1e5 + 10; // 范围开大的,防止出意外
LL v[N] , val[N];
LL n , d;


int main()
{
    /* 正常读入 */
    cin >> n >> d; 
    for (int i = 1; i < n; i ++ ) cin >> v[i];
    for (int i = 1; i <= n; i ++ ) cin >> val[i];
    
    double dis = 0; // dis两个要加油的站点的距离,虽说距离一定是整数,但为了向上取整还是用了double
    LL mi = 1 , Vdis = 0 , sum = 0; /*  
                                        mi存遍历到当前油价最小的站点位置,
                                        Vdis额外的距离(加油开完两个站点后还能开的距离)
                                        sum存总费用
                                    */
    for (int i = 1; i < n; i ++ )   //  注意不用取到n,因为n是最后一个站点,不需要加油
    {
        dis = 0;                    //  距离记得清零
        if(val[i] < val[mi])        //  找到当前油价最小的
        {
            for (int j = mi; j < i; j ++ ) dis += v[j]; //  将两个站点之间的距离统计一下
            sum += val[mi] * ceil((dis - Vdis) / d);    //  向上去整((两站点距离-剩余距离)/每升油能开的距离)
            Vdis += ceil((dis - Vdis) / d) * d - dis;   //  增加剩余距离
            mi = i;
        }
    }
    dis = 0;    //  dis清零(很关键, (^-^))
    for (int j = mi; j <= n; j ++ ) dis += v[j]; // 统计最后加油的站点到最后一站的距离
    sum += val[mi] * ceil((dis - Vdis) / d);    //  增加总费用,同上
    cout << sum;    //正常输出(^-^)
}