CF1654E
- 给定一个长度为 \(n\) 的序列 \(a\)。
- 问至少需要修改几个数才能使得 \(a\) 变为一个等差数列。
- \(n\leq 10^5\)，\(1\leq a_i\leq 10^5\)。
-
我们可以发现值域 \(\leq 10^5\) 实属可疑，我们可以就这点进行分析
-
考虑对于序列的公差 \(d\)，如果 \(d\) 太大的话经过若干轮就会超过原数的值域，之后的所有数都一定会被修改
-
因此我们可以对 \(d\) 进行根号分治
-
当 \(d \leq \sqrt n\) 时，我们设当前从 \(a_i\) 开始，那么有 \(a_0 = a_i - i \times d\)，那我们可以枚举 \(d\) 和 \(i\)， 把 \(a_0\) 放到桶中求众数
-
当 \(d > \sqrt n\) 时，原序列中的数 \(\leq \sqrt n\) 个。我们枚举首项 \(a_i\)，则有 \(a_i - i \times d = a_j - j \times d\)，移向整理得 \(d = \frac{a_i - a_j}{i - j}\)，那么我们就枚举首项 \(a_i\) 和向后枚举 \(\sqrt n\) 个数，求 \(\frac{a_i - a_j}{i-j}\) 的众数即可
-
-
最终复杂度 \(O(n \sqrt n)\)