题解 | 小红的平滑值插值

不难想到, 如果相邻两数之差大于k, 且我们要插入若干个数使得相邻之差不大于k, 那么一定平均的插入最优, 选择

a_i, a_i + k, a_i + 2 * k, a_i + 3 * k, ..., a_{i + 1}

这样的方法最优

令 a_i 和 a_{i + 1} 之差为 dif , 则插入次数等于 ceil(dif / k) - 1, 遍历计算即可

注意原数组中的 max_dif < k 的情况,这种时候我们需要额外插入元素来满足题目限制

不难证明只需要插入一个元素, 在任意位置插入 min(a_i, a_i + 1) + k 即可

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    i64 n, m;
    std::cin >> n >> m;
    i64 ans = 0;
    std::vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    i64 mx = 0;
    for (int i = 2; i <= n; i++) {
        i64 dif = std::abs(a[i] - a[i - 1]);
        mx = std::max(mx, dif);
        ans += std::max((dif + m - 1) / m - 1, 0ll);
    }
    if (mx < m) {
        ans++;
    }
    std::cout << ans << "\n";
    return;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
mx = 0

for i in range(n - 1) :
    dif = abs(a[i] - a[i + 1])
    mx = max(mx, dif)
    ans += max((dif + m - 1) // m - 1, 0)

if mx < m :
    ans += 1

print(ans)