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

· · 题解

题目简述

将序列修改为：单调递增等差数列、单调递减等差数列或常数序列（公差为0的等差数列），并使修改的卡片数量最少。

思路介绍

核心思路是找到与原序列匹配元素最多的等差数列，因为最少修改次数 = 总元素数 - 最大匹配数。

一个等差数列由首项 a_1 和公差 d 决定，第 k 项为 a_1 + k\times d。若原序列中两个元素 x_i 和 x_j(i < j) 属于该数列，则满足：

x_j - x_i = (j - i) \times d

因此，公差 d = \frac{x_j - x_i}{j - i}，且 d 必须为整数（修改后的数据为整数）。

枚举可能的等差数列。遍历所有可能的元素对 (i, j)\space (i < j)，计算对应的 d。若 x_j - x_i 不能被 j - i 整除，则跳过（d 非整数，无效）。否则，根据 x_i 和 d 计算首项 a_1 = x_i - i \times d，确定该等差数列。

对每个有效等差数列，遍历整个序列，统计满足 x_k = a_1 + k\times d 的元素个数，记录最大值。

最少修改次数 = 总元素数 N - 最大匹配数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> x(N);
    for (int i = 0; i < N; ++i) {
        cin >> x[i];
    }

    int cnt = 1; // 最少有1个元素匹配（极端情况）

    // 枚举所有可能的i < j对，确定等差数列的d和a1
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int dx = x[j] - x[i];
            int dj = j - i;

            // 公差d必须为整数，否则跳过
            if (dx % dj != 0) {
                continue;
            }
            int d = dx / dj;
            // 计算首项a1：第i项为a1 + i*d = x[i] → a1 = x[i] - i*d
            int a1 = x[i] - i * d;

            // 统计该等差数列在原序列中的匹配数
            int cnt1 = 0;
            for (int k = 0; k < N; ++k) {
                if (x[k] == a1 + k * d) {
                    cnt1++;
                }
            }

            // 更新最大匹配数
            if (cnt1 > cnt) {
                cnt = cnt1;
            }
        }
    }

    // 最少修改次数 = 总元素数 - 最大匹配数
    cout << N - cnt << endl;

    return 0;
}