CF1365B Trouble Sort 题解

description：

• 给定一个长度为 $n$ 的序列 $a_i$ 和每个元素的属性 $b_i$。

• 一次操作定义为一对 $(i,j)$ 满足 $b_i\neq b_j$ 时，交换 $a_i,a_j$。（属性也随之交换）

• 你需要求出这个序列能否由若干次（可以为 $0$）操作后得到一个不降序列。

• 输入有多组数据。数据组数不超过 $100$。 $1\le n\le 500$，$1\le a_i\le 10^5$，$b_i\in \{0,1\}$。

• translate by @ShineEternal。

solution：

这道题可以观察到一个十分有趣的属性：只要 $0$ 和 $1$ 都存在，那么这个序列一定能由一些操作后得到不降序列。

否则如果序列最开始已经是不降序列了，也是 Yes。

其余情况就是 No 了。

code：

#include<cstdio>
using namespace std;
int a[505],b[505];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		int flag0=0,flag1=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&b[i]);
			if(b[i]==0)
			{
				flag0=1;
			}
			if(b[i]==1)
			{
				flag1=1;
			}
		}
		if(flag0==1&&flag1==1)
		{
			printf("Yes\n");
			continue;
		}
		flag1=0;
		for(int i=2;i<=n;i++)
		{
			if(a[i-1]>a[i])
			{
				printf("No\n");
				flag1=1;
				break;
			}
		}
		if(flag1==0)
		printf("Yes\n");
	}
}