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

一道模拟题

题意

有

N

张卡片按左右一排排列。每张卡片上写有一个整数，第

i

张卡片上写的整数是

A_i

（

1\le i\le N

）。你可以从这

N

张卡片中选择若干张卡片删除，同时剩下卡片的顺序保持不变。

移除若干张卡片后，如果剩下卡片中从左数第

x

张卡片上写的数正好等于

x

，那么我们称该卡片为“原位卡片”。如果所有剩下的卡片都是原位卡片，那么我们称卡片序列达到了“原位状态”。要求，计算为了使卡片序列达到“原位状态”，至少需要移除多少张卡片。

分析

创建

a

数组存储数据，以及

f1

，

f2

两个标记变量，分别标记：

数组是否本来就满足要求。
数组是否有 $1$ (因为“原位状态”必须从 $1$ 开始，没有 $1$ 需要全部删除)。

先遍历一遍数组，如果本来就满足要求直接输出

0

结束，如果没有

1

直接输出

n

结束。

如果以上特殊条件均不满足，则定义变量

k

，令

k=1

，再遍历一遍数组发现 a[i]==k 就让 k++，最后

n-(k-1)

的值就是最后要达到“原位状态”需删除的最少的卡片数量。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[250005];
int f1=0,f2=0,k=1;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	for(int i=1;i<=n;i++){
		if(a[i]!=i)f1=1;//本来就满足要求 。
		if(a[i]==1)f2=1;//没有 1 那么就需要全部删除 。
	}
	if(f1==0){
		cout<<0;return 0;
	}
	else if(f2==0){
		cout<<n;return 0;
	}
	
	for(int i=1;i<=n;i++){
		if(a[i]==k){
			k++; 
		}
	}
	cout<<n-(k-1);
	return 0;
}

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

文章操作

题意

分析

代码

相关推荐

评论

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