智乃的跳跃排序 - 题解

📋 题目描述

给定一个长度为 的数组，数组的值互不相同。现在只能交换下标或者值的差值为 的元素。具体来说，对于 ，如果 或者 ，则可以交换 的值。

问：是否能在这个限制条件下实现升序排序？

🤔 问题分析

核心思想

这是一个关于连通性的问题。我们需要判断所有元素是否能通过给定的交换规则到达它们最终排序后的位置。

交换规则分析

  1. 下标差为 k：位置 和 可以交换
  2. 值差为 k：值为 和 的元素可以交换

关键洞察

  • 如果元素 可以通过交换规则到达位置 ，那么元素 也可以到达位置
  • 这形成了一个模 的等价类
  • 对于每个等价类，我们只需要检查：原始位置模 的分布 是否等于 目标位置模 的分布

💡 解题思路

  1. 建立映射：

    • mp[value] = index：原始值到原始位置的映射
    • mp2[value] = index：排序后值到目标位置的映射

  2. 按值分组：

    • 将所有值按照模 的余数分组
    • 对于每个组，检查原始位置和目标位置的模 分布是否一致

  3. 连通性检查：

    • 对于每个未访问的值，找到它所在的等价类
    • 统计等价类中原始位置和目标位置的模 分布
    • 如果分布不一致，则无法排序

🔧 算法步骤

1. 读取输入：n, k 和数组 a[]
2. 建立原始值到位置的映射：mp[a[i]] = i
3. 排序数组得到目标状态
4. 建立排序后值到位置的映射：mp2[a[i]] = i
5. 对于每个未访问的值：
   a. 找到它所在的等价类（通过 +k 跳跃）
   b. 统计等价类中原始位置的模 k 分布
   c. 统计等价类中目标位置的模 k 分布
   d. 如果分布不一致，输出 "No"
6. 如果所有等价类都通过检查，输出 "Yes"

📝 代码解析

#include<bits/stdc++.h>
using namespace std;
int a[101010];
map<int,int>vis;        // 标记已访问的值
map<int,int>mp,mp2;     // mp: 原值->原位置, mp2: 排序后值->目标位置

int main(){
    int n,i,k;
    cin>>n>>k;
    
    // 建立原始映射
    for(i=0;i<n;i++)cin>>a[i],mp[a[i]]=i;
    
    // 排序得到目标状态
    sort(a,a+n);
    
    // 建立目标映射
    for(i=0;i<n;i++)mp2[a[i]]=i;
    
    // 检查每个等价类
    for(i=0;i<n;i++){
        if(!vis[a[i]]){
            map<int,int>s;  // 统计模 k 的分布差异
            
            // 遍历当前等价类中的所有值
            for(int p=a[i];mp.count(p);p+=k){
                s[mp[p]%k]++;    // 原始位置模 k 计数 +1
                vis[p]=1;        // 标记已访问
            }
            
            // 检查目标位置分布
            for(int p=a[i];mp.count(p);p+=k){
                s[mp2[p]%k]--;   // 目标位置模 k 计数 -1
                if(s[mp2[p]%k]<0)return cout<<"No",0;  // 分布不一致
            }
        }
    }
    
    cout<<"Yes";
    return 0;
}

🔍 关键点解释

1. 等价类的构建

for(int p=a[i];mp.count(p);p+=k)

通过不断加 找到所有与 在同一个等价类中的值。

2. 分布统计

s[mp[p]%k]++;    // 原始位置的模 k 分布
s[mp2[p]%k]--;   // 目标位置的模 k 分布

通过加法和减法来统计分布差异。如果最终所有 都为 0，说明分布一致。

3. 连通性判断

如果某个模 的计数变为负数，说明目标位置的需求超过了原始位置的供给，无法完成排序。

⏰ 复杂度分析

  • 时间复杂度：，主要由排序决定
  • 空间复杂度：，用于存储映射和访问标记

🎯 示例分析

示例1：

排序后：

等价类分析：

  • 模5余0：无元素
  • 模5余1： → 位置0→位置0 ✓
  • 模5余2： → 位置1→位置1 ✓
  • 模5余3： → 位置0→位置2 ✗ (无法从位置0跳到位置2)
  • 模5余4： → 位置3→位置3 ✓
  • 模5余0： → 位置4,5→位置4,5 ✓

结果：No（因为3无法到达目标位置）

示例2：

排序后：

等价类分析：

  • 所有元素的原始位置模分布 = 目标位置模分布

结果：Yes

💭 总结

这道题巧妙地运用了模运算和连通性的思想。关键在于理解交换规则形成的等价类结构，以及如何高效地检查每个等价类内的位置分布是否一致。

通过这种分析，我们可以将复杂的交换问题转化为简单的数学统计问题，大大简化了求解过程。

难度等级：Medium-Hard
算法标签：数学、贪心、连通性
时间复杂度：
空间复杂度：