P9749

cosf · 2023-11-01 23:24:41 · 个人记录

P9749 公路

话说本次 CSP J 和 S 出的 T2 都是原题的极其弱化版。

思路

就是一个特别板的贪心。每到一个站，就选择之前的最便宜的那一个站加就可以了，只用确保到下一个站。

不用 dfs，也不用分支语句（min 函数除外），也不用多余的数组，只用递推即可。具体的加油量使用类似高精除的方法即可，不需要浮点数。

极简代码

// O(n)
#include <iostream>
using namespace std;

#define MAXN 100005

using ll = long long;

ll v[MAXN];
ll d;

int n;

int main()
{
    cin >> n >> d;
    for (int i = 1; i < n; i++)
    {
        cin >> v[i];
    }
    ll r = 0, mn = 0x3ffff3fff3fff3ff; // 余数，最便油价
    ll res = 0;
    for (int i = 1; i < n; i++)
    {
        ll a;
        cin >> a;
        mn = min(mn, a);
        int b = ((v[i] - r) + d - 1) / d;
        res += b * mn;
        r = b * d + r - v[i];
    }
    cout << res << endl;
    return 0;
}