E. Sakurako, Kosuke, and the Permutation - 题解
比赛与标签
比赛: Codeforces Round 981 (Div. 3) 标签: brute force, data structures, dfs and similar, dsu, graphs, greedy, math 难度: *1400
题目大意喵~
Kosuke酱因为考试没考好，心里不平衡，就想偷偷溜进 Sakurako 的房间，把她心爱的排列 p 搞乱，让它变成一个“简单排列”的说。
一个排列是“简单”的，需要满足对于每一个位置 i，要么 p[i] = i（自己指向自己），要么 p[p[i]] = i（和另一个数相互指向）。
Kosuke 每次操作可以交换排列中任意两个位置 p[i] 和 p[j] 的值。他想知道，最少需要多少次交换才能把这个排列变成一个“简单排列”呢？
输入就是一个排列的长度 n 和这个排列 p。我们需要输出最少的交换次数，喵~
思路分析喵~
这道题看起来有点复杂，但只要我们把它转换成一个更熟悉的问题，就会豁然开朗啦，呐！
核心思想: (排列与环) 一个排列
p其实可以看作一个有向图，喵~ 我们可以从每个数字i向p[i]连一条有向边。因为每个数字都恰好出现一次，所以这个图会由若干个互不相交的环组成。举个栗子：
p = [2, 3, 4, 5, 1]1 -> 22 -> 33 -> 44 -> 55 -> 1这就形成了一个大环：1 -> 2 -> 3 -> 4 -> 5 -> 1。
那什么是“简单排列”呢？
p[i] = i对应到图上，就是i -> i，这是一个长度为 1 的环（自环）。p[p[i]] = i对应到图上，如果p[i] = j且i != j，那么p[j] = i。也就是i -> j并且j -> i，这是一个长度为 2 的环。
所以，题目的目标就是：用最少的交换次数，把图中所有长度大于 2 的环，都拆分成长度为 1 或 2 的环，的说喵！
关键观察: (如何拆环最高效？) 我们只需要关注那些长度
k >= 3的环，因为长度为 1 和 2 的环已经是“简单”的了，不需要动它们。那么，对于一个长度为
k的环，怎么用最少的交换来拆解它呢？- 一个长度为
k的环，最少需要k-1次交换才能把它完全拆成k个自环。但这可能不是最优的，因为我们也可以拆成 2-环。 - 贪心策略: 我们的目标是每次交换都能“解决”掉尽可能多的元素。一次交换最多能影响两个元素
p[i]和p[j]。 - 让我们来试试看！考虑一个长度为
k的环c1 -> c2 -> ... -> ck -> c1。 - 我们可以通过一次交换，把这个
k-环拆成一个(k-2)-环 和一个2-环。比如，我们交换p[c1]和p[c3]的值。原来p[c1]=c2,p[c3]=c4。交换后p'[c1]=c4,p'[c3]=c2。新的环变成了c1 -> c4 -> ... -> ck -> c1(一个k-2环) 和c2 -> c3 -> c2(一个2-环)。 - 这个操作非常高效！我们用 1 次交换 就把一个
k-环变成了一个更小的(k-2)-环和一个已经“简单”的2-环。 - 我们可以重复这个过程，每次都把环的长度减 2，直到环的长度小于等于 2。
所以，对于一个长度为
k（k>=3）的环，我们需要多少次交换呢？k=3: 1 次交换 -> 1个1-环 和 1个2-环。需要1次。k=4: 1 次交换 -> 2个2-环。需要1次。k=5: 1 次交换 -> 1个3-环 和 1个2-环。剩下的3-环还需要1次。总共2次。k=6: 1 次交换 -> 1个4-环 和 1个2-环。剩下的4-环还需要1次。总共2次。
喵~ 发现规律了吗？对于一个长度为
k的环，需要的交换次数是(k-1) / 2(这里是整数除法哦！)。(3-1)/2 = 1(4-1)/2 = 1(5-1)/2 = 2(6-1)/2 = 2这个公式完美地描述了我们的贪心策略，的说！
- 一个长度为
算法流程:
- 创建一个
visited数组，来标记哪些数字已经被我们探查过了。 - 遍历从
1到n的所有数字i。 - 如果
i还没有被访问过（!visited[i]），说明我们发现了一个新的环的起点！ - 从
i开始，沿着p指示的边一直走下去（current = p[current]），直到回到一个已经访问过的节点。同时，记录下这个环的长度cycle_length。 - 根据我们刚才发现的公式，计算拆分这个环需要的交换次数：
(cycle_length - 1) / 2。 - 把这个次数累加到总交换次数
total_swaps上。 - 将这个环上的所有节点都标记为已访问。
- 遍历结束后，
total_swaps就是我们要求的最小总交换次数啦！
- 创建一个
代码实现
#include <iostream>
#include <vector>
#include <numeric>
void solve() {
int n;
std::cin >> n;
std::vector<int> p(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> p[i];
}
// 用一个 visited 数组来标记每个节点是否已经被某个环包含，喵~
std::vector<bool> visited(n + 1, false);
int total_swaps = 0;
// 遍历所有节点，寻找并处理每一个环
for (int i = 1; i <= n; ++i) {
// 如果当前节点还没被访问过，说明它属于一个我们尚未发现的新环
if (!visited[i]) {
int current = i;
int cycle_length = 0;
// 沿着 p[i] 的指向一直走，直到回到环的起点，计算环的长度
while (!visited[current]) {
visited[current] = true; // 标记为已访问
cycle_length++;
current = p[current]; // 跳到环的下一个节点
}
// 核心计算步骤！喵~
// 一个长度为 k 的环，需要 (k-1)/2 次交换才能拆成长度为1或2的环。
// 整数除法在这里非常巧妙：
// k=1: (1-1)/2 = 0
// k=2: (2-1)/2 = 0
// k=3: (3-1)/2 = 1
// k=4: (4-1)/2 = 1
// ...以此类推，正好符合我们的分析结果，的说！
total_swaps += (cycle_length - 1) / 2;
}
}
std::cout << total_swaps << "\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) 的说。 我们在主循环中遍历从
1到N的所有数字。对于每个数字，我们只会在它所属的环被发现时访问它一次。因为所有环是不相交的，所以每个数字总共只会被访问和标记一次。因此，总的时间复杂度是线性的，与N成正比。空间复杂度: O(N) 的说。 我们需要一个大小为
N+1的向量p来存储排列，还需要一个大小为N+1的布尔向量visited来记录访问状态。所以空间开销是线性的。
知识点总结
解决这个问题，我们主要用到了以下几个可爱的知识点，的说喵~
- 排列的环分解 (Permutation Cycle Decomposition): 理解任何一个排列都可以看作是若干个不相交的环的集合，这是解决这类问题的基础视角。
- 图的遍历 (DFS/BFS): 我们寻找环的过程，本质上就是在由排列构成的有向图上进行深度优先搜索（DFS）。
- 贪心算法 (Greedy Algorithm): 我们发现了每次用一次交换将
k-环拆成(k-2)-环和2-环是最优的局部策略，并最终导向了全局最优解。 - 数学观察与归纳: 通过分析小数据，推导出
(k-1)/2这个通用公式是解题的关键一步，呐！