算法
(暴力枚举、几何) $O(t * n^3)$
这题显然是想让我们把原序列变成等差数列
第一想法是枚举公差,但看到样例 $4$ 。。。(开始挠头
注意到等差数列有个很好的几何性质,就是 $d = \frac{a_j - a_i}{j - i}$,可看作是直线的斜率,$a_k - a_i = d \cdot (k - i)$ 可看成是一个直线方程。又由于 $a_k - a_i$ 为整数,所以 $j - i \mid (a_j - a_i) \cdot (k - i)$
再注意到 $n$ 只有 $70$,于是我们可以枚举两个点得到斜率对应的分子和分母,并讨论每个点是否在这条直线上,从而得出最多有多少个点位于同一条直线,最后用 $n$ 减去这个数字便是我们需要修改的数的个数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
inline void chmax(int& x, int y) { if (x < y) x = y; }
void solve() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int ans = 1;
rep(j, n)rep(i, j) {
int now = 0;
rep(k, n) {
int y = (a[j] - a[i]) * (k - i);
int x = j - i;
if (y % x == 0 and a[i] + y/x == a[k]) now++;
}
chmax(ans, now);
}
cout << n - ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}