平滑值(pinghua)
平滑值
题目描述
一个数组的“平滑值”定义为：相邻两数差的绝对值的最大值。
具体的，数组a的平滑值定义为
f ( a ) = m a x i = 1 n − 1 ∣ a i + 1 − a i ∣ f(a)=max_{i=1}^{n-1}|a_{i+1}-a_i| f(a)=maxi=1n−1∣ai+1−ai∣
现在小红拿到了一个数组。她每次操作可以在两个元素之间添加一个整数（不能添加在第一项前面或者最后一项后面）。小红希望最终数组的平滑值恰好等于 k k k，你能帮小红求出最小的操作次数吗？
输入格式
第一行输入两个正整数 n , k n,k n,k，代表数组的大小、以及最终希望达到的平滑值。
第二行输入 n n n个正整数 a i a_i ai。代表小红拿到的数组。
输出格式
一个整数，代表小红最少的操作次数。
样例 #1
样例输入 #1
5 2
1 4 5 1 3
样例输出 #1
2
提示
小红首先在1和4之间插入一个3或2，然后在5和1之间插入一个3即可。
数据范围
2 ≤ n ≤ 1 0 5 2≤n≤10^5 2≤n≤105
1 ≤ k , a i ≤ 1 0 9 1≤k,a_i ≤10^9 1≤k,ai≤109
/*
分三种情况：
1.max(abs(a[i]-a[i-1]))==k,不用改变，输出 0
2.max(abs(a[i]-a[i-1]))<k,只在某一段做 1 次就行
3.max(abs(a[i]-a[i-1]))>k,枚举每一大于 k 的段，次数为
max/k(向上取整)-1,累加起来就是答案
*/
#include<bits/stdc++.h>
using namespace std;
int n, k;
int main() {cin >> n >> k;vector<int> a(n + 1);int mx = 0;for (int i = 1; i <= n; i++) {cin >> a[i];if (i > 1) mx = max(mx, abs(a[i] - a[i - 1]));//前后数字的最大差值}if (mx < k)cout << 1;else if (mx == k) cout << 0;else {long long ans = 0;//注意要开 long longfor (int i = 2; i <= n; i++) {int now = abs(a[i] - a[i - 1]);if (now <= k)continue; //小于等于 k 不处理ans += (now + k - 1) / k - 1; //向上取整先加k-1，再除以 k，得到段数，减 1 就是个数}cout << ans;}return 0;
}