【2024东区信息学小学组】3.刷题顺序（prob）

Question

【2024东区信息学小学组】3.刷题顺序（prob）
描述

为了在某谷上挑战 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~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
提示

样例中一共有三组数据：
1.第一组数据中 K = 2，意味着 Jimmy 每次只能交换两道位置间隔为 2 的题。Jimmy可以先交换第 1 题和第 3 题，交换后的题难度为 1 4 3 3 4。然后再交换第 2 题和第 4 题，交换后的题难度为 1 3 3 4 4，刚好是从小到大排序的，因此输出一行 yes；
2.第二组数据中，不存在任何操作方案，使得题按难度从小到大排序，因此输出一行
no；
3.第三组数据中，题本来就是按照难度从小到大排序的，Jimmy 不用做任何交换操作，因此输出一行 yes。

【测试点约束】
对于 100% 的数据，满足 1 ≤ T ≤ 5，1 ≤ N ≤ 5000，1 ≤ K < N ，1 ≤ Di ≤ 109。

Answer 1

让【宝码香车】来帮你解答，本回答参考DeepSeek编写，并整理提供。
如果还有疑问可以点击头像关注私信或评论。如果答案让您满意，请采纳、点赞、关注，非常感谢！

问题分析

我们需要判断给定的数组是否可以通过交换间隔为K的元素来排序成非递减序列。关键在于理解交换操作的性质以及如何利用这些操作来排序数组。

关键观察

1. 交换操作的性质：每次交换只能交换位置相差K的两个元素。这意味着数组可以被分成K个独立的子序列：

   • 第0个子序列：位置0, K, 2K, ...
   • 第1个子序列：位置1, K+1, 2K+1, ...
   • ...
   • 第K-1个子序列：位置K-1, 2K-1, 3K-1, ...

   每个子序列内部的元素可以通过交换操作任意排列，但不同子序列之间的元素不能直接交换。

2. 排序条件：要使得整个数组可以排序成非递减序列，每个子序列内部的元素必须能够独立排序，且所有子序列排序后的结果拼接起来就是整个数组的排序结果。

解决步骤

1. 分割子序列：将原数组分割成K个子序列。
2. 排序子序列：对每个子序列单独排序。
3. 拼接并检查：将排序后的子序列按原始位置重新拼接成新数组，检查新数组是否是非递减的。

代码实现

def solve():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        N, K = map(int, input[ptr:ptr+2])
        ptr +=2
        d = list(map(int, input[ptr:ptr+N]))
        ptr +=N
        
        # Split into K groups
        groups = [[] for _ in range(K)]
        for i in range(N):
            groups[i % K].append(d[i])
        
        # Sort each group
        for g in groups:
            g.sort()
        
        # Reconstruct the array
        sorted_d = []
        for i in range(N):
            group_idx = i % K
            elem_idx = i // K
            sorted_d.append(groups[group_idx][elem_idx])
        
        # Check if sorted
        is_sorted = True
        for i in range(1, N):
            if sorted_d[i] < sorted_d[i-1]:
                is_sorted = False
                break
        print("yes" if is_sorted else "no")

solve()

代码解释

1. 输入处理：使用sys.stdin.read快速读取所有输入数据，并通过指针ptr逐个处理每组数据。
2. 分割子序列：将原数组d分割成K个子序列，每个子序列包含位置模K相同的元素。
3. 排序子序列：对每个子序列单独进行排序。
4. 拼接数组：按照原始位置将排序后的子序列重新拼接成新数组sorted_d。
5. 检查排序：检查sorted_d是否是非递减的，如果是则输出yes，否则输出no。

复杂度分析

• 时间复杂度：每组数据的时间复杂度为O(N log N)，因为需要对K个子序列分别排序，每个子序列的长度约为N/K，总排序时间为O(K * (N/K) log (N/K)) = O(N log (N/K))，最坏情况下为O(N log N)。
• 空间复杂度：O(N)，用于存储子序列和拼接后的数组。

示例验证

以样例输入的第一组数据为例：

• 输入：5 2，3 4 1 3 4
• 子序列：
  • 第0组：3, 1, 4 → 排序后：1, 3, 4
  • 第1组：4, 3 → 排序后：3, 4
• 拼接后：1, 3, 3, 4, 4 → 非递减，输出yes。

其他样例类似验证即可。