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

Gilbert1206 · 2025-06-04 22:12:17 · 题解

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

题目传送门

思路

这道题要求你最少移开多少个数保证剩下的数 i=a_i，此时的 i 是从 1 开始的。这道题明显是一道贪心的水题，我们只需要知道离前面一个 a_{i-1} 最近的并且在它的后面的 a_i 有没有就可以了。如果有，说明了我只需要记录 a_i 中 i 的位置以便下一个寻找是否拥有，如果没有，说明了我们不管怎么删都只有 1 至 i-1 个数可以通过删除来达到 i=a_i 了。

code

#include<bits/stdc++.h>
using namespace std;
int a[270000],b[270000];
int main(){
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=260000;i++){
        b[i]=1e9;
    }//初始化
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(b[a[i]-1]!=1e9&&b[a[i]]==1e9){//如果 b[a[i]-1] 没有被标记过下标，则说明我们此时不需要标记。如果 b[a[i]] 被标记过说明它不是离 b[a[i]-1] 的最短。
            b[a[i]]=i;
        }
    }
    for(int i=1;i<=260000;i++){//从 1 开始直到 b[i] 没有被标记过。
        if(b[i]==1e9){
            cout<<n-ans;
            return 0;
        }
        ans++;
    }
    return 0;
}