门户类网站模板平面设计网站建设

平滑值

题目描述

一个数组的“平滑值”定义为：相邻两数差的绝对值的最大值。
具体的，数组a的平滑值定义为
$f(a)=ma{x}_{i=1}^{n-1}|a_{i+1}-a_i|$

现在小红拿到了一个数组。她每次操作可以在两个元素之间添加一个整数（不能添加在第一项前面或者最后一项后面）。小红希望最终数组的平滑值恰好等于$k$，你能帮小红求出最小的操作次数吗？

输入格式

第一行输入两个正整数$n,k$，代表数组的大小、以及最终希望达到的平滑值。

第二行输入$n$个正整数$a_i$。代表小红拿到的数组。

输出格式

一个整数，代表小红最少的操作次数。

样例 #1

样例输入 #1

5 2
1 4 5 1 3

样例输出 #1

2

提示

小红首先在1和4之间插入一个3或2，然后在5和1之间插入一个3即可。

数据范围

$2\le n\le 10^5$

$1\le k,a_i\le 10^9$

/*
分三种情况：
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;
}