自动搬运

查看原文

来自洛谷，原作者为

	Gilbert1206 班尼特厨||xf20280303||原神UID:331504998||CSP-S 冲 220+ || CSP-J AK||互关：/paste/cxk74r5i

搬运于2025-08-24 23:17:30，当前版本为作者最后更新于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;
}