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

chen_kun · 2025-06-04 19:19:51 · 题解

2025.6.10 修改了错别字。

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

一道很简单的题。

思路简述

用变量 cnt 代表要删几个数。

直接遍历整个 a 数组，顺带加上一个变量 j 代表当前想要达到原位状态则最后一个数应为 j。若 a_i 的值为 j 则代表 a_i 可以作为当前原位状态的最后一个数，变量 j 就要加一。如果 a_i 的值不为 j，那就要把它删掉，变量 cnt 就要加一。

代码呈现

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t,cnt;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,j=1;i<=n;i++){
        cin>>t;
        if(t==j) j++;//如果可以作为原位状态的一个数则j加一 
        else cnt++;//否则要删掉，cnt加一 
    }
    cout<<cnt;
    return 0;
}

The end.