题目描述
https://codeforces.com/contest/1453/problem/B
Solution
感觉不像是 $div2 B$ 的难度
我们将数组差分，然后发现后缀操作相当于将某一个数加一或者减一，最后我们要让所有数都变成 $0$
那么答案就是每个数绝对值
但是我们注意到可以改变某一个数，直接枚举改变哪个数即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#define maxn 200010
#define maxm 100010
#define ll long long
#define pb push_back
#define cn const node
#define cQ const Queue
using namespace std;
int n, m, a[maxn], d[maxn];
void work() {
cin >> n; ll sum = 0, ans;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 2; i <= n; ++i) sum += abs(a[i] - a[i - 1]);
ans = sum - abs(a[2] - a[1]);
for (int i = 2; i < n; ++i)
ans = min(ans, sum - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]));
ans = min(ans, sum - abs(a[n] - a[n - 1]));
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|