JZTXT

【题解】CF1819A Constructive Problem

发布时间 2023-09-11 21:35:05作者: ricky_lin

你考虑这道题中判 No 显然有两种情况：

  • 如果说 mex 是 n 的话，即我们的所有数都是必不可少不能更改的，那么就是 No
  • 如果说原序列中有 mex+1 那么我们就可以发现添加 mex 显然会有很大的问题，我们显然要将所有的 mex+1 的区间替换为 mex，并且保证其他的数的 mex 和原序列的 mex 相同。

code:

#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
int t,n;
int a[NN];
int b[NN];
int sta[NN],top;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);top = 0;
		for(int i = 1; i <= n; ++i) scanf("%d",&a[i]),b[i] = a[i];
		sort(b+1,b+1+n);
		int mex = 0;
		for(int i = 1; i <= n; ++i)
			if(b[i] == mex) ++mex;
		if(mex == n){puts("No");continue;}
		for(int i = 1; i <= n; ++i) if(a[i] == mex+1) sta[++top] = i;
		if(top == 1 || top == 0){puts("Yes");continue;}
		int cnt = 0;
		for(int i = 1; i < sta[1]; ++i) b[++cnt] = a[i];
		for(int i = sta[top] + 1; i <= n; ++i) b[++cnt] = a[i];
		sort(b+1,b+1+cnt);
		int mex2 = 0;
		for(int i = 1; i <= cnt; ++i)
			if(b[i] == mex2) ++mex2;
		if(mex2 == mex) puts("Yes");
		else puts("No");
	}
	return 0;
}