算法
(构造) $O(n)$
这题本质上是求消除某个数字之后的影响。
首先我们可以先求出未更改数字之前的最小操作次数,记为 $x$,不难看出它等于原数组的差分数组除去第一项的和。
其次,分析需要减少一个数最大能减少多少次操作,记为 $y$。
对于 $a_0$ 来说,把它替换成 $a_1$ 是最佳操作,从而可以减少 $|a_1 - a_0|$ 次操作;同样地,对 $a_{n-1}$ 来说,把它替换成 $a_{n-2}$ 是最佳操作,从而可以减少 $|a_{n - 1} - a_{n - 2}|$ 次操作。然后对于剩余元素,更改 $a_i$ 会影响到 $|a_{i} - a_{i - 1}|$ 和 $|a_{i+1} - a_i|$。然后注意到,对于 $a_{i-1}, a_{i}, a_{i+1}$,$a_i$ 总是极值点,把 以 $a_i$ 开始的后缀通过若干次第一个(或第二个)操作后 变成 $a_i$ 变成 $a_{i-1}$,还需对以 $a_{i+1}$ 开始的后缀进行第二个(或第一个)操作以补偿额外的操作,所以最佳操作是把 $a_i$ 替换成 $a_{i-1}$,从而可以减少 $|a_{i} - a_{i-1}| + |a_{i+1} - a_i| - |a_{i+1} - a_{i-1}|$ 次操作。
于是
所以,最后的答案等于 $x - y$。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::max;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& it : a) cin >> it;
int64_t x = 0;
for (int i = 0; i + 1 < n; ++i) {
x += abs(a[i + 1] - a[i]);
}
int y = max(abs(a[1] - a[0]), abs(a[n - 1] - a[n - 2]));
for (int i = 1; i + 1 < n; ++i) {
y = max(y, abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i]) - abs(a[i + 1] - a[i - 1]));
}
cout << x - y << '\n';
}
return 0;
}