专栏文章

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

DDragonForge
P12696题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip50xsj
此快照首次捕获于
2025/12/03 06:16
3 个月前
此快照最后确认于
2025/12/03 06:16
3 个月前
查看原文

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

其实这一题并不难。题目要求删除原数组中的部分元素，使得剩下的每个元素与它的下标相同。这里可能还不能发现什么突破口，但是题目中有这样一句话：
请注意，如果将所有卡片都移除，总是可以达到原位状态。
怎样才会要把所有元素都删除呢？发现如果不存在 1 这个数字的话一定不可能构成目标数列。以此类推，从左往右扫描原数组，以此找到 1 2 3 4……最后找到数字几，就代表删除后可以剩下几个数字，那么删除的个数就是用 n 减去前面得到的剩下的数字，有图为证。
贴上代码，
CPP
#include <bits/stdc++.h>

using namespace std;

const int MAXN=2.5e5+10;

int n,a[MAXN],cnt=1;

int main(void){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin.tie(0)->sync_with_stdio(false);
	cout.tie(0)->sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==cnt){
			++cnt;
		}
	}
	cout<<n-(cnt-1);
	return 0;
}

完结散花！！！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...