首页 > 试题广场 >

小美的陡峭值操作

[编程题]小美的陡峭值操作
  • 热度指数：780 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
定义一个数组的的陡峭值为：相邻两个元素之差的绝对值之和。
现在小美拿到了一个数组，她可以最多进行1次操作：选择一个区间，使得区间内所有元素加1。
小美希望最终数组的陡峭值尽可能小，你能帮帮她吗？

输入描述:
第一行输入一个正整数t，代表询问次数。
对于每次询问输入两行：
第一行输入一个正整数n，代表数组长度。
第二行输入n个正整数a_i，代表小美拿到的数组。
1\leq t \leq 1000
2\leq n \leq 10^5
1\leq a_i \leq 10^9
保证所有询问的n的总和不超过10^5


输出描述:
输出t行，输出一个整数，代表该次查询陡峭值的最小值。
示例1

输入

2
5
1 4 2 3 4
3
1 2 1

输出

5
1

说明

第一组询问，选择[3,4]区间即可，数组变成{1,4,3,4,4}。
第二组询问，选择[1,1]区间即可，数组变成{2,2,1}。
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 16:59:59
题目链接 小美的陡峭值操作 题目描述 给定一个数组 ，其“陡峭值”定义为相邻元素之差的绝对值之和，即 。 我们最多可以执行一次操作：选择一个连续的子数组（区间），并将区间内的所有元素都加 1。 目标是找到一个最优的操作（或者不操作），使得最终数组的陡峭值尽可能小。 解题思路 这是一个最优化问题。一个 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 数组 前缀和 美团
难度：
2条回答 432浏览

热门推荐

相关试题

小美的陡峭值操作

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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