#XMOJ11807. 麻烦的排序
麻烦的排序
说明
时间限制:1 Sec
内存限制:256 MB
输入文件:sort.in 输出文件:sort.out
小明的桌上有 $n$ 张卡片排成一行,从左到右编号为 $1$ 到 $n$。每张卡片上写着一个数字 $a_i$,并且卡片有颜色 $b_i$:$b_i = 0$ 表示红色,$b_i = 1$ 表示蓝色。
小明可以执行任意多次操作,每次操作:选择两张颜色不同的卡片并交换它们的位置。
请问小明能否通过若干次这样的操作,把所有卡片按数字非递减的顺序排好(即任意相邻两张满足左边的数字不超过右边的数字)?
输入格式
第一行一个整数 $T$,表示测试组数。
每组数据占三行:第一行一个整数 $n$;第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$;第三行 $n$ 个整数 $b_1, b_2, \dots, b_n$(每个数为 $0$ 或 $1$)。
输出格式
每组数据输出一行:如果能够排好,输出 YES;否则输出 NO。
样例
样例 1
1
4
28 77 65 86
1 0 1 0
YES
样例说明:
这组卡片中既有红色()又有蓝色()。因为不同颜色的卡片可以交换,而两张同色卡片也能借助一张另一颜色的卡片中转完成交换,所以所有卡片都可以任意重排,一定可以按数字排好,输出 YES。
样例 2
1
3
5 4 6
1 1 1
NO
样例说明:
三张卡片全是蓝色,没有可以交换的对象,只能保持原样。而原顺序 中 5 > 4,不满足非递减,所以输出 NO。
数据范围
$1 \le T \le 10$,$1 \le n \le 2 \times 10^5$,$1 \le a_i \le 10^9$,$b_i \in \{0, 1\}$。
所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。
相关
在下列比赛中: