Minimum Swap 题解

skyx · 2025-12-13 21:53:19 · 题解

Minimum Swap 题解

简要题意

这个题目很不说人话。

给你一个排列 P，最少需要 K 次交换才能排好。在所有能用“最少交换次数”把排列 P 排成有序的方案中，有多少种不同的“第一步交换 (i,j)”是合法的？保证 P 不等于 (1,2,\ldots,N)。

题目分析

oiwiki - 置换和排列

排列 P = (P_1, P_2, \dots, P_N) 本质上就是一个从位置到位置的映射，表示原来应该放数字 i 的位置，现在放了数字 P_i。

我们考虑把这些把数写成若干个不相交的环（轮换表示），比如样例一：

5
3 1 4 2 5

就分成了 (1,3,4,2), (5) 这两个环。

明显的是，在一个环里，所有的数都放错了位置，但只在这几个位置之间循环。不同环之间的数互不影响。

设这个置换分解成了 c 个环（长度为 1 的也算）。

一个关键结论：一个长度为 L 的环，最少需要 L-1 次交换就能全部放对。

直观理解：

一个环里有 L 个元素都错位在这 L 个位置中。
可以选环中的某个位置，每次把应该放到这的元素换进来。
每交换一次，环里就有一个位置被永久修正。
修正完 L 个位置，只需要 L-1 次（最后一个自然就对了）。

所以总最少交换次数：

K=\sum_{\text{每个环}}(L_k-1)=\left(\sum L_k\right)-c=N-c

发现 K 和环的个数有关，那么一次环内交换会怎样改变环的数量？

因为每交换一次，环里就有一个位置被永久修正，可以当作“分”出去了一个环，所以环数 c' = c+1。于是做一次环内交换，K 就会变小，于是如果能，在第一步（实际上是每一步）操作时，做环内交换是更优的。

于是答案就是：在一个环里的整数对 (i,j) 的个数。

而每个环中能组成的合法对数是：

\text{环内点对数} = \binom{L}{2} = \frac{L\times (L - 1)}{2}

把所有环的结果加起来，就是最终答案。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int N=300006;
int p[N];
bool vis[N];
signed main()
{
    int sti=clock();

//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>p[i];
    }
    ll ans=0;

    for(int i=1; i<=n; i++)
    {
        if(vis[i]) continue; // 已经访问过的点跳过
        int cur=i;
        int sz=0; // 当前环的大小
        while(!vis[cur])
        {
            vis[cur]=1;      // 标记访问
            sz++;            // 环长度 +1
            cur=p[cur];      // 跳到下一个点
        }
        ans+=1ll*sz*(sz-1)/2; // 累加本环的点对数
    }

    cout<<ans<<endl;

//  cerr<<1.0*(clock()-sti)/CLOCKS_PER_SEC<<endl;
    return 0;
}