题目描述
https://codeforces.com/contest/1654/problem/E
简要题意：给定一个长度为 $n$ 的序列 $a_i$，每次操作可以选择一个 $i$ 将 $a_i$ 变成任意一个整数，求最小需要多少次操作可以整个序列变成一个等差数列
$n,a_i\le 10^5$
Solution
注意到 $a_i\le 10^5$，也就是说公差一定是 $10^5$ 范围内，另外如果公差为 $d$，那么可能可以保留的子区间的长度就是 $\frac{10^5}{d}$，容易想到根号分治
枚举公差 $d$，如果公差小于 $\sqrt n$，那么我们直接暴力整个序列 $a_i$，将 $a_i$ 减掉 $i\times d$，相同大小的数的个数的最大值即为可以保留的数，时间复杂度 $O(n\sqrt n)$
如果公差大于 $\sqrt n$，我们知道子区间的长度一定小于 $\sqrt n$，所以我们枚举所有长度为 $\sqrt n$ 的子区间，我们认为一定保留区间左端点 $a_l$，那么对于一个 $a_i$，如果 $a_i-a_l$ 能够被 $i - l$ 整除的话，那么对于公差 $\frac{a_i-a_l}{i-l}$，$a_i$ 才能被保留，我们把 $a_i$ 贡献到这个公差上即可，这里的时间复杂度就是 $O(n\sqrt n)$
总时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n\sqrt n)$
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
38
39
40
41
42
43
44
45
46
47
48
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#define maxn 100010
#define maxm 40000010
#define ll long long
using namespace std;
int n, a[maxn];
int cnt[maxm];
int solve() {
int ans = n, blo = 340;
for (int d = 0; d <= blo; ++d) {
int mx = 0;
for (int i = 1; i <= n; ++i)
mx = max(mx, ++cnt[a[i] + (n - i) * d]);
ans = min(ans, n - mx);
for (int i = 1; i <= n; ++i)
cnt[a[i] + (n - i) * d] = 0;
}
int m = 340;
for (int i = 1; i < n; ++i) {
int mx = 0;
for (int j = i + 1; j <= min(n, i + m - 1); ++j)
if (a[j] > a[i] && (a[j] - a[i]) % (j - i) == 0)
mx = max(mx, ++cnt[(a[j] - a[i]) / (j - i)]);
for (int j = i + 1; j <= min(n, i + m - 1); ++j)
if (a[j] > a[i] && (a[j] - a[i]) % (j - i) == 0)
cnt[(a[j] - a[i]) / (j - i)] = 0;
ans = min(ans, n - mx - 1);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
int ans = solve();
reverse(a + 1, a + n + 1); cout << min(ans, solve()) << "\n";
return 0;
}
|