题解 | 小红的平滑值插值(C++)

我们首先在输入的时候用绝对值差分数组预处理一下两相邻数字之间绝对值之差，然后用max_element就能获取到题目中所说的f（a）

显然有以下三种情况：

1.f（a）= k，那么一次处理都不需要，输出0

2.f（a）< k，那么在数组中任意挑选2个相邻的数，让其中较小的那个加上k，f（a）自然就会变成k

3.f（a）> k，那么需要再遍历出比k大的绝对值差分（比k小的不影响f（a）大小，无需处理）,如果绝对值差分d[i]能整除k，那么需要在这相邻的2个数之间加入d[i] / k - 1个数，也就是操作d[i] / k - 1次；如果不能整除，那么相应的就是要操作d[i] / k次，将它们累加起来得到ans

时间复杂度O（n），不会超时

c++实现代码如下：（代码里有一些自己的板子内容，不必在意）

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long
// #define ctz __builtin_ctzll  // 不 define int long long记得删
// #define clz __builtin_clzll  // 不 define int long long记得删
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e5 + 10;
const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll a[N], d[N];

void Aiden()
{
    ll m, n, sum = 0, ans = 0, num, i, j, k, mi = INF, ma = -INF, cnt = 0, x, y, len;
    cin >> n >> k;
    for (i = 1; i <= n;i++)
    {
        cin >> a[i];
        d[i] = abs(a[i] - a[i - 1]);
    }
    m = *max_element(d + 1,d + n + 1);
    if (m < k)
    {
        cout << 1 << endl;
        return;
    }
    if (m == k)
    {
        cout << 0 << endl;
        return;
    }
    for (i = 2; i <= n; i++)
    {
        if (d[i] > k)
        {
            if (d[i] % k == 0)
                ans += d[i] / k - 1;
            else
                ans += d[i] / k;
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // LiangBaiKai();
    int _ = 1;
    // cin >> _;
    while (_--)
        Aiden();
    return 0;
}