题解 | 小红的平滑值插值

/*汪汪汪*/
.    𐚁へ         ╱|𐚁
   ૮ -  ՛ )      (`  - 7
    /  ⁻ ៸|       |、⁻〵
乀 (ˍ,   JJ     じしˍ,)ノ
/*汪汪狗，喵呜~，可爱捏*/
好了，进入正题，这道题也是非常简单了，笨笨狗都会做的题，喵呜~，首先读懂题目，使平滑值恰等于k，那么我们直接遍历，找到大于k的值，就插入数字，至于要插入几个数字呢，喵呜~，提问！！！，汪，我们首先想到用差值除以k，但笨笨狗发现遇到能够整除的情况要减一，那么我们能不能和为一种情况呢，注意到，汪，统一成向上取整-1，我们可以这样想，将长度为差值的一段数分成长度为k的组，一共有几组，要插入的数即为组数-1，在注意到,这个题的ans可能很大，要开ll，汪，最后，ans 为0的情况，可能是平滑值恰为k，也可能是平滑值小于k，所以要特判一下。汪汪汪，笨笨狗的讲解就到这里了，喵呜~，午安！
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    int n,k;cin >> n >> k;
    vector<int> a(n);
    for(int & k : a) cin >> k;
    ll ans = 0;
    int fd = 0;
    for(int i = 0; i <n - 1;i++) {
        if(abs(a[i + 1] -a[i]) > k) ans += (abs(a[i + 1] - a[i]) + k - 1) / k - 1;
        if(abs(a[i + 1]- a[i]) == k) fd =1;
        // cout << ans << "\n";
    }
    if(ans == 0 && fd == 0) cout << 1 << "\n"; 
    else cout << ans << "\n";
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}