自动搬运

查看原文

来自洛谷，原作者为

	Rachitis **

搬运于2025-08-24 23:17:31，当前版本为作者最后更新于2025-06-04 20:06:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面：P12697 [KOI 2022 Round 2] 更换卡片

本蒟蒻只会枚举 qwq。

看到 $N = 500$ 的数据范围，我们直接开始暴力枚举。考虑从每一个数作为我们的原点，再选择另外一个数作为我们计算等差数列的标准，判断这个公差是否为整数。如果是整数，就进行数列的遍历，对于不符合标准的项进行修改，并用修改次数来更新最小次数。如果第二个数没有找到，则说明我们需要将整个数列都修改成同一个值。总时间复杂度为 $O(n^3)$。

更具体地，我们在数组 $a$ 中挑选出一个数，下标记为 $i$，然后再从数列中找出另一个个数，下标记为 $j$，用这两个数作为我们等差数列的标准。此时，公差 $d = \frac{a[i] - a[j]}{i - j}$。

如果 $d$ 是一个整数，那么就开始遍历整个数组。对于第 $k$ 个数，应满足 $a[k] = a[i] + (k - i) \times d$。如果不满足，则增加一次修改次数，最后更新答案。如果 $i = j$，则说明我们需要将整个数组都修改成同一个值，即 $a[i]$。

最终就可以输出最小的修改次数啦。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, a[510], ans, minx = 1e9;
int main(){ 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            ans = 0;
            if (i == j){
                for (int k = 1; k <= n; k++){
                    if (a[k] != a[i]){
                        ans++;
                    }
                }
            }
            else if (abs(a[i] - a[j]) % abs(i - j) == 0){
                int c = ((a[i] - a[j]) / (i - j));  
                for (int k = 1; k <= n; k++){
                    if (a[k] != a[i] + (k - i) * c){
                        ans++;
                    }
                }
            }
            else continue;
            minx = min(minx, ans);
        }
    }
    cout << minx;
    return 0;
}