A1769.排序
入门
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小A 有一个由 n 个整数组成的数组 a,他希望 AC 狗按照非递减的顺序重新对数组进行排序。由于这对 AC 狗来说太容易了,小 A 只允许 AC 狗使用下面的操作:
- 选择数组的下标 i 和 j,如果 ∣i−j∣≥x,则可以交换元素 ai 和 aj。
请你帮 AC 狗判断,是否可以使用上面的操作让数组变为一个有序序列(非递减)。
输入格式
每个测试包含多个测试用例。
第一行包含测试用例的数量 T (1≤T≤100)。
每个测试用例的第一行包含两个整数 n 和 x (1≤x≤n≤105)。
每个测试用例的第二行包含 n 整数 a1 ~ an(1≤ai≤109)。
输出格式
如果 AC 狗可以使用上面的操作让数组变为一个有序序列(非递减),则输出 YES
。否则,输出 NO
。
输入输出样例
输入#1
4 3 3 3 2 1 4 3 1 2 3 4 5 2 5 1 2 3 4 5 4 1 2 3 4 4
输出#1
NO YES YES YES
说明/提示
第一个测试用例中,任何一个元素都不能交换,无法排序。
第二个测试用例中,数组已经有序。
第三个测试用例中,可以进行如下操作:
- [5,1,2,3,4],swap(a1,a3)
- [2,1,5,3,4],swap(a2,a5)
- [2,4,5,3,1],swap(a2,a4)
- [2,3,5,4,1],swap(a1,a5)
- [1,3,5,4,2],swap(a2,a5)
- [1,2,5,4,3],swap(a3,a5)
- [1,2,3,4,5]