题意
给定长度为n {n}n的数组a {a}a，给定x {x}x。将1 − n {1-n}1−n插入到数组a {a}a中，求代价最小。
代价： ∣ a i + 1 − a i ∣
思路
发现：1−x之间插入2−(x−1) 造成的代价是0，所以插入1和x之后其之间的值都可以插在内部，不造成影响。因此只需考虑1和x。
先找到数组的最小值mn，最大值mx。
1插入的情况：
在mn左右：abs(1−mn)∗2
数组首：abs(1−a.front())
数组尾：abs(1−a.back())
x插入的情况：
在mx左右：abs(x−mx)∗2
数组首：abs(x−a.front())
数组尾：abs(x−a.back())
但是x
都取其最小的选择即可。
样例
输入
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
代码
int n, x; void solve() { scanf("%lld %lld", &n, &x); vector<int> a(n, 0); for (int &v: a) scanf("%lld", &v); int mx = *max_element(all(a)), mn = *min_element(all(a)); int sum = 0; for (int i = 0; i < n - 1; i++) sum += abs(a[i + 1] - a[i]); int xx = min({abs(1 - mn) * 2, abs(1 - a.front()), abs(1 - a.back())}); int yy = 0; if(mx < x) yy = min({abs(x - mx) * 2, abs(x - a.front()), abs(x - a.back())}); printf("%lld\n", sum + xx + yy); } signed main() { int _ = 1; scanf("%lld", &_); while(_--) { solve(); } return 0; }
