首页 > 试题广场 >

小红的平滑值插值

[编程题]小红的平滑值插值
  • 热度指数：2145 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红定义一个数组的“平滑值”为：相邻两数差的绝对值的最大值。
具体的，数组a的平滑值定义为f(a)=max_{i=1}^{n-1}|a_{i+1}-a_i|

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

输入描述:
第一行输入两个正整数n,k，代表数组的大小、以及最终希望达到的平滑值。
第二行输入n个正整数a_i。代表小红拿到的数组。
2\leq n \leq 10^5
1\leq k,a_i \leq 10^9


输出描述:
一个整数，代表小红最少的操作次数。

示例1

输入

5 2
1 4 5 1 3

输出

2

说明

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

算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 162浏览

热门推荐

相关试题

小红的平滑值插值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号