题解 | 小红的平滑值插值

首先考虑当前数组a的平滑值小于k的情况，这时我们可以选取任意的区间[i,i+1]，其中i<=1<=n-1，选择在下标i和i+1中间插入值min(a[i],a[i+1])+k，就可以构造出数组a的平滑值刚好等于k的情况。

再考虑当前数组a的平滑值大于k的情况，此时存在若干区间[j,j+1]使得abs(a[j+1]-a[j])>k，思考一下如何插值可以使得总答案次数最小，我们会想到贪心地插差值绝对值刚好为k的数会比较合适。举例：如样例中下标1的值a[1]=1和下标2的值a[2]=4，它们差值绝对值为3，我们就可以插入一个值min(a[1],a[2])+k；再看样例中下标为3的值a[3]=5和下标为4的值a[4]=1，它们差值绝对值为4，我们也只需要插入min(5,1)+2=3；考虑若此时存在差值绝对值为5应该需要插入几个数，应该是2个，如往数值1和6之间插入3和5。我们归纳总结一下，发现如果存在相邻两个数的差值绝对值大于k时，我们需要插入ceil(d/k)-1个数，其中ceil表示上取整函数，而d表示相邻两个数的差值绝对值。

最后观察数据范围，发现答案极有可能爆int，因此答案要开long long。而上述操作总的来说只会遍历一遍1~n，时间复杂度为O(n)，不会超时。

#include <iostream>
#include <vector>

using i64 = long long;

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

  int n,k;
  std::cin >> n >> k;

  std::vector<int> a(n);
  for(int i = 0; i < n; i++){
    std::cin >> a[i];
  }

  i64 ans = 0;
  int maxDiff = 0;

  for(int i = 0; i < n-1; i++){
    maxDiff = std::max(maxDiff,std::abs(a[i+1]-a[i]));
    int d = std::abs(a[i+1]-a[i]);
    if(d <= k){
      continue;
    }

    ans +=(d+k-1)/k-1;
  }

  if(maxDiff < k){
    std::cout << "1\n";
    return 0;
  }

  std::cout << ans << "\n";
}