A1445 | 排序
来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
小$A$ 有一个由 $n$ 个整数组成的数组 $a$，他希望 $AC$ 狗按照非递减的顺序重新对数组进行排序。由于这对 $AC$ 狗来说太容易了，小 $A$ 只允许 $AC$ 狗使用下面的操作：
* 选择数组的下标 $i$ 和 $j$，如果 $|i-j| \geq x$，则可以交换元素 $a_i$ 和 $a_j$。
请你帮 $AC$ 狗判断，是否可以使用上面的操作让数组变为一个有序序列（非递减）。
* 选择数组的下标 $i$ 和 $j$，如果 $|i-j| \geq x$，则可以交换元素 $a_i$ 和 $a_j$。
请你帮 $AC$ 狗判断，是否可以使用上面的操作让数组变为一个有序序列（非递减）。
输入格式
每个测试包含多个测试用例。
第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。
每个测试用例的第一行包含两个整数 $n$ 和 $x$ ($1 \le x \le n \le 10^5$)。
每个测试用例的第二行包含 $n$ 整数 $a_1$ ~ $a_n$($1 \le a_i \le 10^9$)。
第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。
每个测试用例的第一行包含两个整数 $n$ 和 $x$ ($1 \le x \le n \le 10^5$)。
每个测试用例的第二行包含 $n$ 整数 $a_1$ ~ $a_n$($1 \le a_i \le 10^9$)。
输出格式
如果 $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(a_1,a_3)$
* $[2,1,5,3,4] ，swap(a_2,a_5)$
* $[2,4,5,3,1] ，swap(a_2,a_4)$
* $[2,3,5,4,1] ，swap(a_1,a_5)$
* $[1,3,5,4,2] ，swap(a_2,a_5)$
* $[1,2,5,4,3] ，swap(a_3,a_5)$
* $[1,2,3,4,5]$
第二个测试用例中，数组已经有序。
第三个测试用例中，可以进行如下操作：
* $[5,1,2,3,4] ，swap(a_1,a_3)$
* $[2,1,5,3,4] ，swap(a_2,a_5)$
* $[2,4,5,3,1] ，swap(a_2,a_4)$
* $[2,3,5,4,1] ，swap(a_1,a_5)$
* $[1,3,5,4,2] ，swap(a_2,a_5)$
* $[1,2,5,4,3] ，swap(a_3,a_5)$
* $[1,2,3,4,5]$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？