acwing 5308 公路 | vegeone

vegeone
0%

acwing 5308 公路

发表于 更新于 分类于 Valine：

题意

n个点，每个点都可以加整数升油，每个点加油的单价不同，1升油可以行驶d km，求到达终点所要花费的最少金钱

思路

贪心思路，每次遇到单价更少的就用单价更少的加油方式

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve()
{
    int n,d;
    cin>>n>>d;
    vector<int>v(n+1),a(n+1);
    for(int i=1;i<n;++i)cin>>v[i];
    for(int i=1;i<=n;++i)cin>>a[i];
    int sum=0,pre=1e18,cost=0;
    for(int i=1;i<n;++i){
        if(pre>a[i]){
            if(sum<=0){
                int temp=(-sum+d-1)/d;
                cost+=temp*pre;
                sum+=temp*d;
            }
            pre=a[i];
        }
        sum-=v[i];
    }
    if(sum<0)cost+=(-sum+d-1)/d*pre;
    cout<<cost<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)	solve();
    return 0;
}