ABC302G Sort from 1 to 4 [关键性质题]

Description

给定一个长度为 \(N\) 的序列，其中每个元素都是介于 \(1\) 和 \(4\) 之间的整数。

可以进行以下操作任意次（可能为零次）：

• 选择一对整数 \((i, j)\)，其中 \(1≤i<j≤N\)，并交换 \(A_i\) 和 \(A_j\)。

输出使序列 \(A\) 变为非递减序列所需的最小操作次数。

Solution

对于这种交换数字，最小操作数是序列相等，或者什么单调性的题，可以优先想到逆序对和建图。

设原序列为 \(A=(A_1, A_2, ..., A_N)\)，排序后为 \(B=(B_1, B_2, ..., B_N)\)，

根据观察，若 \(A_i\ne B_i\)，则我们用它们代表的数字建边 \(A_i\to B_i\)，

由于每个点的出度和入度都相等，所以最终会形成若干个环，且根据 \(A_i\in [1,4]\) 这重要性质，可知环长不超过 \(4\)，

考虑一个长度为 \(i\) 的环，要把它变为合法，需要 \(i-1\) 步，因此我们优先把长度为 \(2\) 的环交换，接着是 \(3\)，最后是 \(4\)，直接暴力枚举计算贡献即可。

Code

const int N = 2e5 + 5;

int n, a[N], b[N], e[5][5];

void Solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++){
        if(a[i] != b[i]) e[a[i]][b[i]]++;
    }

    ll ans = 0;

    for(int i = 1; i <= 4; i++){
        for(int j = 1; j <= 4; j++){
            if(e[i][j] && e[j][i]){
                ll mn = min(e[i][j], e[j][i]);
                ans += mn;
                e[i][j] -= mn;
                e[j][i] -= mn;
            }
        }
    }

    for(int i = 1; i <= 4; i++){
        for(int j = 1; j <= 4; j++){
            for(int k = 1; k <= 4; k++){
                if(i == j || j == k || k == i) continue;
                if(e[i][j] && e[j][k] && e[k][i]){
                    ll mn = min({e[i][j], e[j][k], e[k][i]});
                    ans += mn * 2;
                    e[i][j] -= mn;
                    e[j][k] -= mn;
                    e[k][i] -= mn;
                }
            }
        }
    }

    ll tmp = 0;
    for(int i = 1; i <= 4; i++){
        for(int j = 1; j <= 4; j++){
            tmp += e[i][j];
        }
    }
    tmp /= 4;
    tmp *= 3;
    ans += tmp;

    cout << ans << endl;
}