D. Insert a Progression(绝对值的性质)

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<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
//1 1 3 3 3
int n,x;
int a[10000400];
void solve()
{
	cin >> n >> x;
	int mi = 1e9;
	int ma = -1e9;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
		mi = min(a[i],mi);
		ma = max(a[i],ma);
	}
	long long res = 0;
	for(int i = 2;i <= n;i++)
	{
		res += abs(a[i]-a[i-1]);
	}
	int t1 = min(abs(a[1] - 1),abs(a[n] - 1));
	int tx = min(abs(a[1] - x),abs(a[n] - x));
	for(int i = 2;i <= n;i++)
	{
		t1 = min(t1,abs(a[i-1] - 1) + abs(a[i] - 1) - abs(a[i] - a[i-1]));
		tx = min(tx,abs(a[i-1] - x) + abs(a[i] - x) - abs(a[i] - a[i-1]));
	}
	if(mi > 1)
	{
		res += t1;
	}
	if(x > ma)
	{
		res += tx;
	}	
	cout<<res<<"\n";
	
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
//4 8 12 16 20 24
//
 
//1 2 3 2
//1 2 2 2 2 3
//