平滑值(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,枚举每一大于 k 的段，次数为
max/k(向上取整)-1,累加起来就是答案
*/
#include
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 long
		for (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;
}