Array Shuffling

发表于 分类于 ，

    数组 $b$ 是数组 $a$ 的一个排列。每次操作只能交换 $b$ 数组的两个元素。一个数组 $b$ 的“难过值”是使 $b$ 复原为 $a$ 的最小操作次数。

    现在给定数组 $a$ ，求出“难过值”最大的数组 $b$（任意一组）。

    $\sum n \leq 2\times 10^5$ 。

Array Shuffling

Created by LXC on Thu Apr 11 15:13:16 2024

https://codeforces.com/problemset/problem/1672/F1

ranting: 2000

tag: constructive algorithms, graphs, greedy

problem

数组 $b$ 是数组 $a$ 的一个排列。每次操作只能交换 $b$ 数组的两个元素。一个数组 $b$ 的“难过值”是使 $b$ 复原为 $a$ 的最小操作次数。

现在给定数组 $a$ ，求出“难过值”最大的数组 $b$（任意一组）。

$\sum n \leq 2\times 10^5$ 。

solution

要尽量少的环，难过值=n-环的个数

让不重复的数一组，形成环，环的个数实际上就是重复次数最多的数的个数。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n; 
    vector<int> a(n), c(n+1);
    for (int& i:a) cin >> i;
    vector<vector<int>> g(n+1);
    for (int i=0; i<n; i++) {
        g[++c[a[i]]].push_back(i);
    }
    vector<int> b(n);
    for (auto& i:g) {
        int sz  = i.size();
        sort(i.begin(), i.end(), [&](int x, int y) {
            return a[x] < a[y]; 
        });
        // cout << i << endl;
        for (int j=0; j<sz; j++) {
            b[i[(j+sz-1)%sz]] = a[i[j]];
            // cout << j << ": " << i[j] << ", " << a[i[j]] << endl;
        }
    }
    // cout << g << endl;
    // cout << b << endl;
    for (int i:b) {
        cout << i << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}