题目描述
给定一个由n个整数组成的序列a₁, a₂, …, aₙ,以及x个额外的整数1, 2, …, x。
需要将这些额外的整数插入到序列a中。每个整数可以插入到序列的开头、结尾,或者任意两个元素之间。
生成的新序列a'的得分定义为相邻元素绝对差的和(即Σ|aᵢ' - aᵢ₊₁'|,其中i从1到n+x-1)。
请找出可能的最小得分。
输入格式
第一行包含一个整数t(1≤t≤10⁴)——测试用例的数量。
每个测试用例的描述如下:
第一行包含两个整数n和x(1≤n,x≤2⋅10⁵)——序列的长度和额外整数的数量。
第二行包含n个整数a₁, a₂, …, aₙ(1≤aᵢ≤2⋅10⁵)。保证序列没有前导零。
保证所有测试用例的n之和不超过2⋅10⁵。
输出格式
对于每个测试用例,输出一个整数——插入额外整数后可能的最小得分。
输入输出样例
输入#1
4
1 5
10
3 8
7 2 10
10 2
6 1 5 7 3 3 9 10 10 1
4 10
1 3 1 2
输出#1
9
15
31
13
说明/提示
以下是示例中得分最小的序列。下划线元素是额外插入的整数。注意也存在其他得分相同的序列。
1, 2, 3, 4, 5, 10
7, 7, 6, 4, 2, 2, 1, 3, 5, 8, 10
6, 1, 1, 2, 5, 7, 3, 3, 9, 10, 10, 1
1, 3, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10
解题思路参考
这道题的关键在于发现一个贪心规律:
如果额外数字的范围[1,x]与原数组的范围[min_a, max_a]有重叠,那么中间重叠部分的数字可以"无代价"地插入到原数组中
只需要考虑插入范围两端的数字(1和x)对总得分的影响
对于1,如果1 < min_a,我们需要找到插入1的最优位置,使得增加的得分最小
对于x,如果x > max_a,同样需要找到插入x的最优位置