题目描述

难度分:$1800$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和一个$1$~$n$的排列$p$。

每次操作，你可以交换$p$中的两个元素。

要使$p$的逆序对个数恰好是$1$，至少要操作多少次？

注：逆序对指满足$i \lt j$且$p[i] \gt p[j]$的$(i,j)$。

输入样例

4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1

输出样例

0
1
3
1

算法

环图

看到这个题就想到了一个经典问题：有一个$1$~$n$的排列$p$，每次可以交换排列中任意两个元素，求将排列$p$排好序所需要的最少交换次数？将这个问题抽象成一个图论问题，从$i$向$p[i]$连一条有向边，整个图一定可以形成若干个环，假设一共有$m$个环，利用下标连续怼使环内有序的最少交换数为$x-1$（其中$x$为环的大小），因此要使$p$有序的操作数为$\Sigma_{i=1}^m(x_i-1)=n-m$。

而排列还剩一个逆序对的时候必然形如$1,2,…,k-1,k+1,k,k+2,…,n$，因此我们枚举$(k,k+1)$，有如下两种情况：

1. 如果$k$和$k+1$在一个环内，那就可以在将$p$排好序的过程中经过仅剩一个逆序对的情况，答案为$n-m-1$。
2. 否则就必须先将$p$排好序，然后再交换一个数对，答案为$n-m+1$。

复杂度分析

时间复杂度

算法的本质就是遍历了一个有向图，由于每个节点只有一条出边，所以遍历图的时间复杂度在$O(n)$级别，这也是整个算法的时间复杂度。

空间复杂度

遍历图的过程中需要一个$root$数组，记录每个节点属于哪个环，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010;
int t, n, p[N];
int root[N];

int solve() {
    int res = 0;
    for(int i = 1; i <= n; i++) {
        int x = i;
        if(!root[x]) {
            // 遍历环
            while(!root[x]) {
                res++;
                root[x] = i;
                x = p[x];
            }
            res--;
        }
    }
    bool flag = false;
    for(int i = 1; i < n; i++) {
        if(root[i] == root[i + 1]) {
            flag = true;
            break;
        }
    }
    if(flag) res--;
    else res++;
    return res;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &p[i]);
            root[i] = 0;
        }
        printf("%d\n", solve());
    }
    return 0;
}