F1. Array Shuffling - 题解

比赛与标签

比赛: Codeforces Global Round 20 标签: constructive algorithms, graphs, greedy 难度: *2000

题目大意喵~

米娜桑，下午好喵~ 今天我们来解决一道非常有趣的构造题哦！(ฅ'ω'ฅ)

题目是这样子的：我们有一个数组 a，然后呢，有人把它打乱变成了一个新的数组 b，b 里面元素的种类和数量和 a 是一样的（也就是 b 是 a 的一个排列）。

我们定义一个叫“悲伤值”的东西，它指的是把数组 b 变回数组 a 所需要的最少交换次数。

我们的任务就是，对于给定的数组 a，找到一个排列 b，使得这个“悲伤值”达到最大！也就是说，我们要把 a 搞得尽可能的“乱”，让它恢复原状的步骤最多！找到任何一个这样的 b 都可以的说。

解题思路分析喵~

想让悲伤值最大，我们得先搞清楚它到底是怎么算的。一个排列要恢复成有序状态（或者说目标状态），最少的交换次数等于 n - c，这里的 n 是数组的长度，c 是这个排列中“环” (Cycle) 的数量。

所以呀，我们的目标 “最大化交换次数” 就变成了 “最小化环的数量”！最理想的情况，就是让所有元素都串成一个大环，这样环的数量 c 就是1，交换次数就是 n-1，达到最大值了喵！

一个元素 b[i] 如果和它目标位置的 a[i] 相同，即 b[i] == a[i]，它就自己构成了一个长度为1的环，也叫作“不动点”。我们肯定不希望出现这种情况，因为这会增加环的数量 c，从而减少悲伤值。

所以我们的核心策略就是：构造一个数组 b，使得对于所有的下标 i，都有 b[i] ≠ a[i]。

那么，怎么才能构造出这样一个完美的 b 呢？一个超级棒的办法就是——排序加循环移位！

让我们一步步来拆解这个方法吧：

绑定数值和位置：直接对数值操作会丢失它们在原数组 a 中的位置信息。所以，我们先把数组 a 的每个元素和它的下标绑在一起，存成 (数值, 原始下标) 这样的对。
统计最大频率：我们需要知道哪个数字出现的次数最多，以及这个次数是多少。我们叫它 max_freq 好了。这一步至关重要，马上你就会知道为什么啦！
按数值排序：把第一步创建的 (数值, 原始下标) 对的列表，按照数值从小到大排序。这样一来，所有相同的数值就会被排在一起，形成连续的块。
循环移位构造 b：这是最核心的魔法！我们现在有一个按数值排好序的列表 s。对于列表中的第 i 个元素 s[i]，它的原始下标是 s[i].second。我们不把它自己的值 s[i].first 放回去，而是从别处“借”一个值。借谁的呢？我们就从这个排好序的列表里，向后跳 max_freq 个位置，把 s[(i + max_freq) % n] 的值借过来！

为什么是 max_freq 呢？因为在排好序的列表 s 中，相同数值最长的连续段长度就是 max_freq。如果我们只移动1位，万一 s[i] 和 s[i+1] 的值相同，那不就产生 b[i] == a[i] 的情况了嘛！通过移动 max_freq 位，我们保证 s[i] 和 s[(i + max_freq) % n] 的值一定不同，因为我们已经跳过了整个相同值的最长连续块！这样就完美地避免了所有“不动点”的产生，让环的数量尽可能的少。

这样一通操作下来，我们就得到了一个超级乱的 b 数组，它的悲伤值是最大的说！

猫娘的魔法代码

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

void solve() {
    int n;
    std::cin >> n;

    // 1. 用 vector<pair> 来存储 (数值, 原始下标) 的说
    std::vector<std::pair<int, int>> s(n);
    // 用 map 统计每个数字出现的次数喵
    std::map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        std::cin >> s[i].first; // 读取数值
        s[i].second = i;       // 记录原始下标
        counts[s[i].first]++;  // 对应数值的频率+1
    }

    // 3. 按照数值对 pair 进行排序
    std::sort(s.begin(), s.end());

    // 2. 找到出现次数最多的那个元素的次数 (max_freq)
    int max_freq = 0;
    for (auto const& [val, num] : counts) {
        if (num > max_freq) {
            max_freq = num;
        }
    }

    // 4. 构造结果数组 b
    std::vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        // 这就是核心的旋转操作！
        // s[i].second 是当前元素在原数组 a 中的位置
        // s[(i + max_freq) % n].first 是我们为这个位置选择的新值
        // 通过循环移位 max_freq 来保证新值和旧值一定不同
        b[s[i].second] = s[(i + max_freq) % n].first;
    }

    // 输出我们构造的数组 b
    for (int i = 0; i < n; ++i) {
        std::cout << b[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 优化一下输入输出速度喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析喵

时间复杂度: O(N log N) 的说。主要的时间开销在于对 (数值, 原始下标) 对的排序，std::sort 的复杂度是 O(N log N)。用 std::map 统计频率也是 O(N log N)（如果换成 unordered_map 可以优化到 O(N)），但排序仍然是瓶颈。剩下的遍历都是 O(N) 的。所以总时间复杂度就是 O(N log N)！
空间复杂度: O(N) 的说。我们创建了一个 vector 来存储 pair，一个 map 来存储频率，还有一个结果数组 b。这些都需要 O(N) 的空间，所以空间复杂度是 O(N) 呢。

知识点与总结

这次我们学到了什么呢？(✧ω✧)

核心思想转换: 这道题最重要的一点，是把 "最大化交换次数" 这个模糊的目标，转化为 "最小化排列环数量" 这个具体的数学模型。这是解决排列组合问题的一个非常经典的思路哦！
构造神技: 通过 “排序 + 循环移位” 的方法来构造一个满足特定条件的排列，是一个非常巧妙且常用的技巧。特别是移位的距离选择为 max_freq，完美地解决了值重复可能导致产生不动点的问题，值得我们学习和记忆！
数据绑定: 使用 pair<int, int> 来同时绑定数值和它的原始位置，是处理这类需要保持原始信息的问题的标配操作，非常实用喵~

总的来说，这是一道结合了贪心思想和构造技巧的好题，需要我们从问题表面深入到底层数学原理进行思考。只要想通了要最小化环的数量，问题就迎刃而解啦！希望大家都能从中学到东西，继续加油喵~！

F1. Array Shuffling - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析喵~ ​

猫娘的魔法代码 ​

复杂度分析喵 ​

知识点与总结 ​