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

Rachitis · 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;
}