CSPJ-2:road

【题目描述】

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

公路上一共有 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…𝑎𝑛 ,分别表示在不同站点加油的价格。

【输出】

输出一行,仅包含一个正整数,表示从站点 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∼58
6∼10103
11∼13105A
14∼16105B
17∼20105

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

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

代码实现:洛谷85分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**************************************************************** 
 * Description: CSP_J_R_2  road
 * Author: Alex Li
 * Date: 2024-07-01 16:23:08
 * LastEditTime: 2024-07-02 10:10:04
****************************************************************/
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main(){
    int a,b,n,d,e,sum=0,c=0;
    bool f;
    cin>>a>>b;
    vector<int> sn(a+1,0);
    vector<int> co(a+1,0);

    for(int i=0;i<a-1;i++){
        cin>>n;
        sn[i]=n;
    }
   
    for(int i=0;i<a;i++){
        cin>>n;
        co[i]=n;
    }
    for(int i=0;i<a-1;i++){
        d=sn[i]-c;
        e=i;
        f=true;
       while(f){
             if(co[i]<co[e+1]){
             d+=sn[e+1];
             if((e+1)==(a-1)){
                sum+=ceil(d/(b*1.0))*co[i];
                cout<<sum;
                return 0;
             }
             e++;
             
        }else{
            sum+=ceil(d/(b*1.0))*co[i];
            if(d%b!=0)c=b-d%b;
            else c=0;
            f=false;
            i=e;
        }
        
     }
    }
    cout<<sum;
}
Scroll to Top