题解 CF1365B 【Trouble Sort】
ShineEternal
2020-06-08 20:33:07
[更佳的阅读效果。](https://vipblog.github.io/sal5L5T03/)
## 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](https://www.luogu.com.cn/user/45475)。
## solution：
这道题可以观察到一个十分有趣的属性：只要 $0$ 和 $1$ 都存在，那么这个序列一定能由一些操作后得到不降序列。
否则如果序列最开始已经是不降序列了，也是 `Yes`。
其余情况就是 `No` 了。
## code：
```cpp
#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");
}
}
```