专栏文章

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

NNancy_Cherry
P12697题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0wwie
此快照首次捕获于
2025/12/02 11:33
3 个月前
此快照最后确认于
2025/12/02 11:33
3 个月前
查看原文

题目简述

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

思路介绍

核心思路是找到与原序列匹配元素最多的等差数列，因为最少修改次数 = 总元素数 - 最大匹配数。
一个等差数列由首项 a1a_1 和公差 dd 决定，第 kk 项为 a1+k×da_1 + k\times d。若原序列中两个元素 xix_i 和 xj(i<j)x_j(i < j) 属于该数列，则满足： xj−xi=(j−i)×dx_j - x_i = (j - i) \times d 因此，公差 d=xj−xij−id = \frac{x_j - x_i}{j - i}，且 dd 必须为整数（修改后的数据为整数）。
枚举可能的等差数列。遍历所有可能的元素对 (i,j) (i<j)(i, j)\space (i < j)，计算对应的 dd。若 xj−xix_j - x_i 不能被 j−ij - i 整除，则跳过（dd 非整数，无效）。否则，根据 xix_i 和 dd 计算首项 a1=xi−i×da_1 = x_i - i \times d，确定该等差数列。
对每个有效等差数列，遍历整个序列，统计满足 xk=a1+k×dx_k = a_1 + k\times d 的元素个数，记录最大值。
最少修改次数 = 总元素数 NN - 最大匹配数。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...