cf-置换环问题

标签：pp int res 置换 交换 cf long 问题 逆序

 

 

Problem - D - Codeforces

题意：

　　给你一个排列组合a数组，你每次操作可以交换某a数组中的某两个元素，求最小交换次数，使得得到的a数组中只含有一个逆序对

解题思路：

　　拓展结论：冒泡排序所需要的最少交换次数就是该数组逆序对的总个数（这题用不到）

　　首先题目要求我们只有一个逆序对，言下之意除了a【i】和a【i+1】这两个元素外其他元素均为有序，因此我们可以先把整个数组排成有序的，然后再用一次交换得出一个逆序对。

　　而如果我们对于每个i建立i和a[i]之间的边，就会得到很多的环，意思是a[i]到他该去的位置，形成一个内部的闭环，而要想使得数组有序，且交换次数最少，交换只会在环内发生，不存在环间的交换

　　例如以下排列

 

 

我们看看那个4个点的环

 

 

 

在排列上，进行交换

 

进行了三次交换，就使得环内有序

 

 言下之意，在一个元素个数为n的环中，需要进行n-1次交换才能使得环内有序

因此我们统计出总环数为res

用此让整个数组有序的最小操作次数为n-res

答案为n-res+1

但是，还有一种情况。

对于上面的4个点的环，我们这样交换

 

此时a【2】和a【3】组成了一个逆序对，少了一步操作且也创造出了一个逆序对，于是总操作次数为n-res-1

 

 也就是，如果环中，有相邻的两个点，那么可以通过减少一次交换，使得其贡献出一个逆序对。

 

代码实现

 

 

#include <bits/stdc++.h>
using namespace std;
const long long maxx = 0x3f3f3f3f3f3f3f3f;
const long long minn = 0xc0c0c0c0c0c0c0c0;
const double pi = 4.0 * atan(1.0);
#define int long long
#define f(i, n, m) for (long long i = n; i <= m; ++i)
#define unf(i, n, m) for (long long i = n; i >= m; --i)
#define kong NULL
#define debug cout << "sss" << endl;

map<int, int> mp;
map<int, int> check;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 10, 0);
    check.clear();
    mp.clear();
    f(i, 1, n)
    {
        cin >> a[i];
        mp[a[i]] = i;
    }
    int ff = 1;
    int res = 0;
    f(i, 1, n)
    {
        if (check[i])
            continue;
        map<int, int> o;
        int pp = i;
        check[pp] = 1;
        while (!o[pp])
        {
            if (o[pp - 1] || o[pp + 1])
                ff = -1;
            o[pp] = 1;
            pp = mp[pp];
            check[pp] = 1;
        }
        res++;
    }
    cout << n - res + ff << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    int _;
    cin >> _;
    while (_--)
    {
        solve();
    }
    // solve();
    return 0;
}

 

标签：pp,int,res,置换,交换,cf,long,问题,逆序
From： https://www.cnblogs.com/shifangchen/p/17043387.html