英文题干

Given a permutation of length n. In one operation, you can choose at most four elements from the permutation and swap their positions arbitrarily. What is the minimum number of operations required to sort the permutation in ascending order?

A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitary order. For example, [2, 3, 1, 5, 4] is a permutation, but [1, 2, 2] is not a permutation (2 appears twice in the array), and [1, 3, 4] is also not a permutation (n = 3 but there is 4 in the array))

Input:

Each test contains multiple test cases. The first line contains the number of test cases . The description of the test cases follows.

The first line of each test case contains an integer , indicating the length of the permutation.

The second line contains a permutation .

It is guaranteed that the sum of across all test cases does not exceed .

Output:

For each test case, output a single integer, indicating the minimum number of operations required to sort the permutation.

中文题干

给定长度为 n 的排列。在一个操作中，您最多可以从排列中选择四个元素，并任意交换它们的位置。按升序对排列进行排序所需的最小操作数是多少？

定义：长度 n 的排列是一个数组，由 n 个从 1 到 n 的不同整数以任意顺序组成。例如，[2，3，1，5，4] 是排列，但 [1，2，2] 不是排列（2 在数组中出现两次），而 [1，3，4] 也不是排列（n = 3，但数组中有 4））

思路

  1. 如果想在最少的次数内完成对换，我们就需要寻找类似"a→b,b→c,c→a"这样的结构，因为这样能一次性换对最多的元素。我们把这样的结构称为“错位环”。所以第一步就是遍历原数组，寻找所有的“错位环”。

  2. 其次，因为单次最多对换4个数。因此有如下策略：

  • 若单个错位环长为2，则一次可以对换两个这种环（可以将这种环的单次贡献次数记为 0.5）；

  • 若单个环长为3或4，我们一次只能换一个，这种环单次贡献次数为 1；

  • 若单个环长度大于4就需要多轮，我们观察到除去最后一轮可以一次将所有全换对，之前的轮次一轮最多换对3个数，因此我们选择将 (环数-4)%3，若能整除，那么对这个环的最优换次数就是 (环长-4)/3+1；若余1，说明最后一轮剩余2个数，依照第一条策略，记贡献为 (环长/3)+0.5；若余2，说明最后两轮剩余6个数（2+4=6），即环刚好被3整除，贡献为 (环长/3)。

  • 最后将总贡献（对换次数）上取整即可

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;

int n, num[maxn];
bool vis[maxn];

void process() {

    // 检测错位的元素
    vector<vector<int>> chains;  // 存储各个错位环
    int cnt = 0;  // 环数
    for (int i = 1; i <= n; i++)
    {
        if (num[i] != i && !vis[i]) {
            vector<int> tmp;
            while (tmp.empty() || num[i] != tmp[0]) {
                tmp.push_back(num[i]);
                vis[i] = 1;
                i = num[i];
            }

            chains.push_back(tmp);
            cnt++;
        }
    }

    double ans = 0;
    // 遍历所有链
    for (int i = 0; i < cnt; i++) {
        if (chains[i].size() > 4) { // 长度大于4的链
            if ((chains[i].size() - 4) % 3 == 0) {  // 一次最多换对三个数 (除了最一次)
                ans += (chains[i].size() - 4) / 3 + 1;
            }
            else {
                ans += chains[i].size() / 3;
                if (chains[i].size() % 3 == 2) {
                    ans += 0.5;
                }
            }
        }
        else if (chains[i].size() == 2) { // 长度2的链
            ans += 0.5;
        }
        else {   // 长度3或4的链
            ans += 1;
        }
    }

    // 转为整数
    if (ans > (int)ans)
        cout << (int)ans + 1 << "\n";
    else
        cout << (int)ans << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> num[i];
            vis[i] = 0;
        }
        process();
    }
    return 0;
}
// Inspired by LJY & LXY