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

本题着重考察边界的处理，极其微妙，注意思维的严谨性

核心思路

核心观察

情况一：原数组最大相邻差 $\ge k$

此时，我们只需将所有相邻差 压缩至不超过 $k$ 。
对于每对相邻元素 $a[i-1], a[i]$ ，设 $d = |a[i] - a[i-1]|$ ：
- 若 $d \le k$ ：无需操作；
- 若 $d > k$ ：需插入若干数，使得每段跳跃 $\le k$ 。
最少插入数为：
$\left\lceil \dfrac{d}{k} \right\rceil - 1 = \begin{cases} \dfrac{d}{k} - 1, & d \bmod k = 0 \\ \left\lfloor \dfrac{d}{k} \right\rfloor, & \text{其余情况} \end{cases}$

情况二：原数组最大相邻差 $< k$

此时所有相邻差都小于 $k$ ，平滑值 $< k$ 。
但我们可以在数组末尾添加一个数（例如 $a_{n-1} + k$ ），使得最后一段差为 $k$ 。
这样，平滑值变为 $\max(\text{原最大差}, k) = k$ ，满足要求。
仅需 1 次操作。

注意：例如 $[1,2,3]$ ，但是k为5，只需要在1,2之间插入6即可。

算法步骤

读入数组 $a$ 和参数 $k$ ；
遍历相邻元素，计算最大差 maxd 和总操作次数 ans；
- 对每个差 $d = |a[i] - a[i-1]|$ ：
  - 若 $d > k$ ，累加插入次数：(d + k - 1) / k - 1 或等价形式；
若 maxd < k，输出 1；
否则，输出 ans。

复杂度分析

时间复杂度： $O(n)$ 单次遍历整个数组，甚至边输入边遍历
空间复杂度： $O(1)$
只需储存数组，当然你也可以 $O(1)$

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int n;cin>>n;
    int k;cin>>k;
    vector v(n,0);
    int ans=0,mx=0;cin>>v[0];
    for(int i=1;i<n;i++){
        cin>>v[i];
        int tem=abs(v[i]-v[i-1]);
        mx=max(mx,tem);
        ans+=tem/k;
        if(tem%k==0&&tem!=0)ans-=1;
    }
    if(mx<k)cout<<1;
    else cout<<ans;
}

流程图

flowchart TD
    A[开始] --> B[读取数组 a 和 k]
    B --> C[初始化 maxd = 0, ans = 0]
    C --> D[遍历数组 i = 1 到 n-1]
    D --> E["计算 d = |a[i] - a[i-1]|"]
    E --> F["更新 maxd = max(maxd, d)"]
    F --> G{d > k?}
    G -- 是 --> H[累加操作次数：ans]
    G -- 否 --> I[无需操作]
    H --> J[继续下一个元素]
    I --> J
    J --> K{i == n-1?}
    K -- 否 --> D
    K -- 是 --> L{maxd < k?}
    L -- 是 --> M[输出 1（在末尾添加一个数使差值=k）]
    L -- 否 --> N[输出 ans]
    M --> O[结束]
    N --> O