CCF认证+蓝桥杯习题训练

贪心

*上取整公式*

*代码展示*

#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;
}