P12696 [KOI 2022 Round 2] 原位卡片

LateSight · 2025-06-04 20:50:50 · 题解

这道题看完以后，刚开始以为是排序+离散化，直到看到这行字：

• 你可以从这 N 张卡片中选择若干张卡片并将其移除。此时，剩下卡片的顺序保持不变。

于是只能请出暴力了。

考虑记录每个 A_i 出现的位置，观察样例，发现一个数可以出现多次，讨论以下两种情况：

1. 当前位置 x 在 A_{i-1} 出现的位置前，不做处理；
2. 当前位置 x 在 A_{i-1} 出现的位置后，更新，找最小的 x 。

最后，计算每两张原位卡之间有多少卡片，即为 x_i-x_{i-1}-1 ，当没有原位卡时，直接减掉剩下所有的卡。

具体代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,a[250010];
struct node{
    int x=0x3f3f3f3f;
    vector<int>v;
}e[250010];
//e[i].x表示i在a[e[i].x]处出现 
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],e[a[i]].v.push_back(i);
    //存入当前数出现过的位置 
    e[0].x=0;//边界初始化 
    for(int i=1;i<=n;i++)
        for(auto x:e[i].v) //枚举位置 
            if(e[i-1].x<x) e[i].x=min(x,e[i].x);
    //如果前一个的数出现的位置在当前数的位置x前，该位置x即可选择 
    for(int i=1;i<=n;i++){
        if(e[i].x==0x3f3f3f3f){ans+=n-e[i-1].x;break;}//没有原位卡了就减掉末尾所有的卡 
        ans+=(e[i].x-e[i-1].x-1);//计算前一张卡与现在的卡之间要删去的卡数 
    }
    cout<<ans;
}