首页 > 试题广场 >

小红的平滑值插值

[编程题]小红的平滑值插值

热度指数：2147 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

输入描述:

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

输出描述:

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

示例1

输入

5 2
1 4 5 1 3

输出

说明

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

算法知识视频讲解

kilomatutinal

发表于 2026-01-10 01:36:33

喵~主人，这道题其实很简单喵！我们只需要把所有大于k的差值列出来，然后看看每个大差值能分成多少段不超过k的小段哦~ 对于每个大差值 i，要分成 i 除以 k 向上取整个小段喵！（小贴士：向上取整公式为（i + k - 1）/ k)但中间需要插入的数字个数要比小段数减一，就是 (i + k - 1) 展开全文

Rain_Fly

发表于 2024-03-24 22:51:16

观察易知，我们存在相邻元素差的绝对值大于k，就需要在中间插入元素，插入元素的个数ans = abs（差值）/K，当差值整除k时间，ans需要减一。我们还需要考虑几个特殊情况: （1）最大差值小于k，输出1即可，我们使用flag标记。（2）最大差值等于k，输出0。注意：一定要开long long 展开全文

BeauWill

发表于 2026-01-10 00:29:31

首先考虑当前数组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]使展开全文

此在Dasein

发表于 2026-01-10 01:10:06

问题分析该问题的核心在于通过最小化插入操作次数，使得数组的平滑值（相邻元素最大差绝对值）恰好等于。这包含两个核心约束：上限约束 (Upper Bound)：修改后的数组中，任意相邻两数的差的绝对值不能超过。存在性约束 (Existence)：修改后的数组中，必须至少存在一对相邻数值，其展开全文

憨憨的竹林

发表于 2026-01-10 02:19:29

我们首先在输入的时候用绝对值差分数组预处理一下两相邻数字之间绝对值之差，然后用max_element就能获取到题目中所说的f（a）显然有以下三种情况：1.f（a）= k，那么一次处理都不需要，输出02.f（a）< k，那么在数组中任意挑选2个相邻的数，让其中较小的那个加上k，f（a）自然就会变展开全文

BaiJay

发表于 2026-01-10 08:34:07

模拟即可 #include <bits/stdc++.h> #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(0); 展开全文

duang0925

发表于 2026-01-10 13:28:23

/*汪汪汪*/ . 𐚁へ ╱|𐚁 ૮ - ՛ ) (` - 7 / ⁻ ៸| |、⁻〵乀 (ˍ, JJ じしˍ,)ノ /*汪汪狗，喵呜~，可爱捏*/ 好了，进入正题，这道题也是非常简单了，笨笨狗都会做的题，喵呜~，首先展开全文

软件25_4刘卓生

发表于 2026-01-14 17:15:11

本题着重考察边界的处理，极其微妙，注意思维的严谨性核心思路核心观察情况一：原数组最大相邻差此时，我们只需将所有相邻差压缩至不超过。对于每对相邻元素，设：若：无需操作；若：需插入若干数，使得每段跳跃。最少插入数为：情况二：原数组最大相邻差此展开全文

_Elysium_

发表于 2026-01-10 01:02:44

不难想到, 如果相邻两数之差大于k, 且我们要插入若干个数使得相邻之差不大于k, 那么一定平均的插入最优, 选择a_i, a_i + k, a_i + 2 * k, a_i + 3 * k, ..., a_{i + 1}这样的方法最优令 a_i 和 a_{i + 1} 之差为 dif , 则插入次数展开全文

YunBaichuan

发表于 2026-01-10 11:07:46

思路：整体思路比较容易想到：当两数间的差值时，用公差为的等差数列去从小到大的插入，结果就是，然后不断累加即可。但是有个特判不好注意到，整体思路可以处理差值中有k的情况，此时会正确输出0；但当所有差值都< k时，此时应该输出1，因为我们要额外构造一个数，使得差值为k。所以说再额外引入一个flag 展开全文

问题信息

难度：

2条回答 8收藏 164浏览

小红的平滑值插值

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题