CCF认证+蓝桥杯习题训练

发布时间:2024年01月13日

贪心

*上取整公式*

(dist + d - 1) / d

*代码展示*

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long LL;

int v[N] , a[N];

int main()
{
    int n , d;
    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 oil = 0;
    LL dist = 0;
    int price = a[1];
    LL ans = 0;
    for(int i = 2; i <= n ;i ++)
    {
        dist += v[i - 1];
        int t = (dist + d - 1) / d - oil;
        oil += t;
        ans += (LL) t * price;
        price = min(price , a[i]);
    }
    
    printf("%ld" , ans);
    
    return 0;
}

文章来源:https://blog.csdn.net/m0_63699273/article/details/135573947
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。