题解：P12696 [KOI 2022 Round 2] 原位卡片

· · 题解

一道模拟题

题目传送门

题意

有 N 张卡片按左右一排排列。每张卡片上写有一个整数，第 i 张卡片上写的整数是 A_i（1\le i\le N）。 你可以从这 N 张卡片中选择若干张卡片删除，同时剩下卡片的顺序保持不变。

移除若干张卡片后，如果剩下卡片中从左数第 x 张卡片上写的数正好等于 x，那么我们称该卡片为“原位卡片”。如果所有剩下的卡片都是原位卡片，那么我们称卡片序列达到了“原位状态”。 要求，计算为了使卡片序列达到“原位状态”，至少需要移除多少张卡片。

分析

创建 a 数组存储数据，以及 f1，f2 两个标记变量，分别标记：

  1. 数组是否本来就满足要求。

  2. 数组是否有 1 (因为“原位状态”必须从 1 开始，没有 1 需要全部删除)。

先遍历一遍数组，如果本来就满足要求直接输出 0 结束，如果没有 1 直接输出 n 结束。

如果以上特殊条件均不满足，则定义变量 k ，令 k=1 ，再遍历一遍数组发现 a[i]==k 就让 k++，最后 n-(k-1) 的值就是最后要达到“原位状态”需删除的最少的卡片数量。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[250005];
int f1=0,f2=0,k=1;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        if(a[i]!=i)f1=1;//本来就满足要求 。
        if(a[i]==1)f2=1;//没有 1 那么就需要全部删除 。
    }
    if(f1==0){
        cout<<0;return 0;
    }
    else if(f2==0){
        cout<<n;return 0;
    }

    for(int i=1;i<=n;i++){
        if(a[i]==k){
            k++; 
        }
    }
    cout<<n-(k-1);
    return 0;
}