CF Global Round 20:F1. Array Shuffling

题目链接：F1. Array Shuffling

题面：

input

2
2
2 1
4

1 2 3 3

output

1 2
3 3 2 1 

题意：给定长度为n的数组a，求一个数组b。可以对b进行交换的 *** 作变成a，记对数组b通过交换变成a的最小 *** 作次数为x。要求构造一个数组b，使得b变为a的最小 *** 作次数最大。

此处有一个结论：排序算法-最少交换次数证明_玉曦的博客-CSDN博客_交换次数最少的排序算法

结论就是：如果想要把a[i]->b[j],我们就建立一个条件i->j

最少 *** 作数=n-环的数量

例如：

a: 1 2 3 4 5 6
b: 4 6 1 3 2 5

 

最少 *** 作数为 n-2 。

那么我们希望最少 *** 作数最多，则希望环的数量最少。

如果需要环最少，每个环中无重复元素，则环的个数其实就等于出现次数最多的次数。

 

那么问题来了，如何求最少的环呢？求了后又该如何记录呢？

环的个数：上面描述中可以发现，重复元素最多的次数，就是环的个数。因为每个环中不能出现重复的元素。所以若x为重复的元素，且重复个数为cnt[x]，那么就会有cnt[x]个环，每个环中都有一个x。

如何记录：可以对a数组进行排序。排序的方式以重复个数最大为优先，同样的重复个数以数大/小为优先。并存入到一个vector vec中

例如对a:5 6 5 6 1 2 1 1排序的话就变成

1 1 1 5 5 6 6 2或者1 1 1 6 6 5 5 2就行。若以第一个排序方式为例。

形成的环一定是1->5->6->1,1->5->6->1,1->2->1。这样的三个环。

定义二维的队列：unordered_map que;

从前向后遍历，每次把后面vec[i+cnt[vec[i]]]的数的数作为vec[i]的后继，并把这个数标记已经在一个环中了。

若发现vec[i+cnt[vec[i]]]已经被标记过了，那么该数的后继就是最大的重复数。

#include 
using namespace std;
const int maxn=2e5+50;
int n;
int a[maxn];
bool st[maxn];
unordered_map cnt;
unordered_map> que;
int cmp(int a,int b){
    if(cnt[a]!=cnt[b]) return cnt[a]>cnt[b];
    return a>b;
}
void solve(){
    cnt.clear();
    scanf("%d",&n);
    int mx=0;
    for(int i=0;i vec;
    for(int i=0;i=n){
            que[t].push(vec[0]);
        }else{
            que[t].push(vec[i+cnt[t]]);
            st[i+cnt[t]]=true;
        }
    }
    for(int i=0;i

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/733469.html