P12696 [KOI 2022 Round 2] 原位卡片

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

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

于是只能请出暴力了。

考虑记录每个

A_i

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

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

最后，计算每两张原位卡之间有多少卡片，即为

x_i-x_{i-1}-1

，当没有原位卡时，直接减掉剩下所有的卡。

具体代码如下：

CPP

#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;
}

P12696 [KOI 2022 Round 2] 原位卡片

文章操作

相关推荐

评论

P12696 [KOI 2022 Round 2] 原位卡片