CSL 的魔法

链接

[https://ac.nowcoder.com/acm/contest/551/E]

分析

很显然就是a的第k大得和b的倒数第k大相乘。

那么我们只要让a的第k大和b的倒数第k大位置是相同的即可

那么如何找最小的移动次数呢？

我们只需要先对a大到小排序，而且保证刚开始的a,b对应位置的元素相对位置没有发生变化

后面就是交换任意两个b中的元素使得b升序最小次数

为什么这样可以呢？

a,b两个同时交换时,因为a和b对应位置的元素值都没变的情况下。a中每个元素对应b的元素都一样的

那么就可以这么做了，算是一种等价形式吧

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

struct str{

    int a,b;

}f[N];

int getMinSwaps(vector<int> &nums){

    //排序

    vector<int> nums1(nums);

    sort(nums1.begin(),nums1.end());

    unordered_map<int,int> m;

    int len = nums.size();

    for (int i = 0; i < len; i++){

        m[nums1[i]] = i;//建立每个元素与其应放位置的映射关系

    }

    int loops = 0;//循环节个数

    vector<bool> flag(len,false);

    //找出循环节的个数

    for (int i = 0; i < len; i++){

        if (!flag[i]){//已经访问过的位置不再访问

            int j = i;

            while (!flag[j]){

                flag[j] = true;

                j = m[nums[j]];//原序列中j位置的元素在有序序列中的位置

            }

            loops++;

        }

    }

    return len - loops;

}

bool cm(str x,str y){

    return x.a>y.a;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int n;

    while(cin>>n){

        vector<int> nums;

       for(int i=0;i<n;i++)

       cin>>f[i].a;

       for(int i=0;i<n;i++)

       cin>>f[i].b;

        sort(f,f+n,cm);

        for(int i=0;i<n;i++)

        nums.push_back(f[i].b);

        int ans=getMinSwaps(nums);

        cout<<ans<<endl;

    }

    return 0;

}