Problem - 1671D - Codeforces

给你一个n个整数的序列a1,a2,...,an。你还得到了x个整数1,2,...,x。

每个整数可以插入序列的开头，也可以插入序列的结尾，或者插入序列的任何元素之间。

所得序列a′的得分是其中相邻元素的绝对差异之和（∑i=1n+x-1|a′i-a′i+1|）。

结果序列a′的最小得分是多少？

输入
第一行包含一个整数t（1≤t≤104）--测试案例的数量。

每个测试案例的第一行包含两个整数n和x (1≤n,x≤2⋅105) - 序列的长度和额外整数的数量。

每个测试案例的第二行包含n个整数a1,a2,...,an（1≤ai≤2⋅105）。

所有测试用例的n之和不超过2⋅105。

输出
对于每个测试案例，打印一个整数--在你插入额外的整数后，序列中相邻元素的最小绝对差值之和。

例子
InputCopy
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
输出拷贝
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–––

题解:
绝对值有一个性质:
假如两个数a < b

对于任何在这两个数之间的数插入不会影响整体的结果

举个例子3  8

8 - 3 = 5

中间插入一个4

4 - 3 = 1

8 - 4 = 4

我们假设ma,mi是原数组的最大值与最小值

那么对结果有影响的只有1 ~ mi-1, ma +1~x

但是如果我们先插入的是1与x,那么其他数就又不用考虑了

所以枚举一下插入的1与x的位置即可

#include
#include
#include
#include
#include