思路
已知任意两项可唯一确定一个等差数列。由于每个 $a_i$ 只能加一、减一或不变,因此对 $a_1, a_2$ 的操作合起来只有 $9$ 种。枚举每种选择,对于由当前选择确定的等差数列 $a^\prime$,对于所有 $i \in [1, n]$,检验 $abs(a^\prime_i - a_i) \le 1$ 是否成立。若均成立,统计需要进行的操作次数,即 $a^\prime_i \ne a_i$ 的个数,用它更新答案。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。
#include <iostream>
#define loop(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
const int N = 1e5 + 10, INF = 1e8;
int n;
int a[N];
int dfs(int x, int y) {
if (x > 1) return INF;
if (y > 1) return dfs(x + 1, -1);
int a1 = a[1] + x, d = a[2] + y - a1;
int res = 0;
loop(i, 1, n) {
// ai 不会爆 int,原因是当 z > 1 时,
// 上个 z = abs(a(i - 1) - a[i - 1]) <= 1
// a(i - 1) <= 1e9 + 1, 而 d <= 1e9 + 1
// ai = a(i - 1) + d <= 2e9 + 2
int ai = a1 + (i - 1) * d;
int z = abs(ai - a[i]);
if (z > 1) return dfs(x, y + 1);
res += z;
}
return min(res, dfs(x, y + 1));
}
int main() {
scanf("%d", &n);
loop(i, 1, n) scanf("%d", a + i);
int res = dfs(-1, -1);
if (res == INF) res = -1;
printf("%d\n", res);
return 0;
}