题解 | 小红的平滑值插值

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e5+5;
ll a[N]; // 存储输入的数组

int main() {
    // 优化输入输出速度（算法无关，属于编程优化技巧）
    cin.tie(0)->sync_with_stdio(0);
    
    // 步骤1：输入基础数据
    ll n,k;          // n：数组长度，k：目标平滑值（要求最终数组平滑值恰好等于k）
    cin>>n>>k;
    for(ll i=1;i<=n;i++){ // 读取原始数组元素
        cin>>a[i];
    }
    
    // 步骤2：初始化核心变量
    ll cnt=0;        // cnt：记录需要插入的元素总数
    ll flag=0;       // flag：记录原始数组中相邻元素的最大差值（用于判断当前平滑值）
    
    // 步骤3：遍历数组，计算需要插入的元素个数（核心逻辑）
    for(ll i=2;i<=n;i++){
        ll t=abs(a[i]-a[i-1]); // 计算当前相邻两个元素的差值绝对值
        flag=max(flag,t);      // 更新全局最大相邻差值（后续用于判断是否需要额外插入）
        
        // 子步骤3.1：如果当前相邻差值超过k，计算需要插入的元素数
        // 插入逻辑：将大差值拆分为多个≤k的小差值，计算需要插入的元素个数
        if(t>k){
            // 例如：差值t=10，k=3 → 10/3=3余1 → 需要插入3个元素（拆分为3,3,4 或 3,4,3）
            // 例如：差值t=9，k=3 → 9/3=3 → 需要插入3-1=2个元素（拆分为3,3,3）
            if(t%k==0){
                cnt+=t/k-1;    // 整除时，插入数=差值/k -1
            }
            else cnt+=t/k;     // 非整除时，插入数=差值/k（向下取整）
        }
    }
    
    // 步骤4：处理特殊情况（核心补漏逻辑）
    // 条件：cnt=0 说明所有相邻差值≤k；flag<k 说明当前数组的平滑值（最大相邻差）小于k
    // 此时需要额外插入1个元素，让某一段相邻差等于k，满足“平滑值恰好等于k”的要求
    if(cnt==0&&flag<k)cnt++;
    
    // 步骤5：输出最终需要插入的元素总数
    cout<<cnt;
    return 0;
}