题解 | #小红的平滑值插值#

问题分析

该问题的核心在于通过最小化插入操作次数，使得数组的平滑值（相邻元素最大差绝对值）恰好等于 $k$ 。

这包含两个核心约束：

上限约束 (Upper Bound)：修改后的数组中，任意相邻两数的差的绝对值不能超过 $k$ 。
存在性约束 (Existence)：修改后的数组中，必须至少存在一对相邻数值，其差的绝对值恰好等于 $k$ 。

由于题目要求“最小操作次数”，且对每一对相邻元素的处理是相互独立的（在两数之间插入数字不会影响这对数之外的其他差值），这显然是一个基于贪心算法 的问题。

核心算法

我们将问题分解为针对每一个相邻数对 $(a_i, a_{i+1})$ 的处理。设当前相邻差值为 $d_i = |a_{i+1} - a_i|$ 。

处理“上限约束” (消除大于 $k$ 的差值)：如果 $d_i > k$ ，则当前的差值破坏了平滑值不超过 $k$ 的条件。我们需要在 $a_i$ 和 $a_{i+1}$ 之间插入若干个整数，将这段距离“切分”成若干个长度不大于 $k$ 的段。
- 最优切分逻辑：为了使操作次数最少，我们应当让每一段的长度尽可能接近 $k$ 。
- 数学推导：将长度 $d_i$ 切分为每段最大长度为 $k$ ，所需的最少段数为 $\lceil d_i / k \rceil$ 。由于每增加一个插入点，段数增加 1，因此需要的插入操作次数为： $\text{ops}_i = \lceil \frac{d_i}{k} \rceil - 1$ 或者在编程中更常用的整数运算公式： $\text{ops}_i = (d_i - 1) // k$ （其中 // 表示整数除法）。
处理“存在性约束” (确保最大值为 $k$ )：
- 情况 A：原始数组的最大差值 $Max(d) > k$ 根据贪心逻辑，我们为了满足上限约束，必须对大于 $k$ 的区间进行切分。只要 $d_i \ge k$ ，我们总能构造出一种切分方案，使得切分后的某一段长度恰好为 $k$ ，其余段长度 $\le k$ 。 例如： $d_i=4, k=3$ 。需插入1个数。我们可以插入一个数使得两段分为 $3$ 和 $1$ 。满足最大值为 3。 因此，如果进行了切分操作，我们可以默认最终的平滑值一定可以取到 $k$ 。
- 情况 B：原始数组的最大差值 $Max(d) == k$ 不需要任何操作，上限和存在性均已满足。操作数为 0。
- 情况 C：原始数组的最大差值 $Max(d) < k$ 此时数组中所有相邻差值都小于 $k$ 。如果不进行操作，最大平滑值小于 $k$ ，不满足目标。我们需要人为地制造一个差值为 $k$ 的相邻对。
  - 我们可以在任意两个数之间插入一个数，使得新构成的两个差值中，最大的那个恰好为 $k$ 。
  - 例如：在 $a, b$ 之间插入 $x$ 。令 $|x-a| = k$ 。由于原差值 $|b-a| < k$ ，根据三角不等式，另一段差值 $|b-x| \le |b-a| + |x-a| < k + k$ 。只要我们选择的 $x$ 合理，只需1次操作即可将平滑值提升到 $k$ （且不破坏上限约束，因为另一段虽然可能变大，但可以通过调整使其 $\le k$ 。实际上更简单的构造是直接插入一个数造成局部“尖峰”）。
  - 结论：如果所有 $d_i < k$ ，我们需要额外增加 1 次操作（除非题目隐含数值必须在 $a_i, a_{i+1}$ 区间内，但题目描述为“插入一个整数”，通常不限制数值范围，且为了满足题目必定有解，允许制造尖峰）。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll k;
    cin >> n >> k;
    vector<ll> diff(n - 1);
    ll maxD = 0LL;
    ll last = 0LL;
    ll res = 0LL;

    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        ll curD = 0LL;
        if (last > 0) {
            curD = abs(a - last);
            if (curD > k)
                res += (curD - 1) / k;
            maxD = max(maxD, curD);
        }
        last = a;
    }

    if (maxD < k) {
        cout << "1\n";
    } else {
        cout << res << "\n";
    }
}