1584. 【2024年中山市东区】刷题顺序（prob）

Question

1. 【2024年中山市东区】刷题顺序（prob）
   (Standard IO)
   时间限制: 1 s 空间限制: 256 MB 具体限制

题目描述
为了在某谷上挑战 Chen，不知何时燃起了雄心壮志的 Jimmy 在某谷上准备好了 N 道题目，打算组建一次正式的比赛，从而把 Chen 难倒。可是，他却在组建比赛时遇到了技术难题。
为了更好地照顾不同层次的参赛者，Jimmy 所出的每道题目都有各自的难度，具体来说，第 i 道题目的难度为 Di。Jimmy 把题目按顺序添加上去后，发现他忘了考虑每道题的难度——Jimmy 当然是希望简单题在前、难题在后的，也就是题目应该按难度从小到大排序，因此他需要调整一下题目的顺序。可是某谷的系统刚好出了问题，只允许他每次对两道位置间隔为 K 的题目交换位置，例如第 1 题和第 K+1 题、第 2 题和第 K+2 题，依次类推。
Jimmy 可不想把辛辛苦苦加好的题目删掉。请你告诉他，经过次数不限的交换位置后（当然也可以不做交换），题目难度能否做到从小到大排好序。

输入
本题有多组数据。
第一行一个正整数 T，表示数组的组数。接下来一共有 2×T 行，为每组数据的具体内容。
每组数据的第一行，为两个正整数 N,K，表示一共有 N 道问题，每次交换只能对两道位置间隔为 K 的问题交换位置。
每组数据的第二行，为 N 个正整数 D1,D2,⋯,DN，表示每道问题的难度。

输出
输出一共 T 行。对于每组数据，如果最终能做到题目按难度从小到大排序，输出一行 yes，否则输出一行 no。

样例数据
输入 #1
3
5 2
3 4 1 3 4
5 3
3 4 1 3 4
7 5
1 2 3 4 5 5 10
输出 #1
yes
no
yes

数据范围限制
对于 100% 的数据，满足 1≤T≤5，1≤N≤5000，1≤K<N，1≤Di≤10^9。

提示
样例中一共有三组数据：

第一组数据中 K=2，意味着 Jimmy 每次只能交换两道位置间隔为 2 的题目。Jimmy 可以先交换第 1 题和第 3 题，交换后的题目难度为 1 4 3 3 4。然后再交换第 2 题和第 4 题，交换后的题目难度为 1 3 3 4 4，刚好是从小到大排序的，因此输出一行 yes；

第二组数据中，不存在任何操作方案，使得题目按难度从小到大排序，因此输出一行 no；

第三组数据中，题目本来就是按照难度从小到大排序的，Jimmy 不用做任何交换操作，因此输出一行 yes。

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

问题分析：

本题需要求出在一个数列中，能否通过多次交换位置，使得数列按照从小到大的顺序排列。

这里需要注意的是，每一次交换只能交换位置间隔为K的两个元素，若K=1，则可随意交换相邻两个元素。

解决方案：

1. 暴力枚举

最简单的想法是，枚举所有情况来判断是否能达到目标状态。对于每组数据而言，时间复杂度为 O(N^2×K)，可能会超时。

1. 排序判断

想要数组每个位置上的数单调不降，那么排序后的数组应该和原数组相同。可以将原数组排序，得到排序后的结果，然后比较该结果是否与原数组相同即可。时间复杂度为 O(NlogN)。

1. 判断单调性

通过观察题目，We can find a truth, which is:交换只允许相隔为 K 的位置，所以我们最多只能将从位置 1 开始的 K 个数间隔地进行单调性改变，接下来开始的下一组 K 个数间隔地进行单调性改变，如此下去，直至数组的最后一组 K 个数。 我们可以通过判断每一组 K 个数是否为单调递增，即可直接判断该数列能否变为单调递增。

代码实现：

C++ 代码：