题解：AT_abc302_g [ABC302G] Sort from 1 to 4

· · 题解

模拟赛里当签到题切的，居然是 ABC 的 G 题。

思路

读入时记录每个元素的初始下标，之后按元素大小排序，找到每个元素排序前的下标对应的排序后元素的值记录个数，共 16 种情况。形象化后，我们就找到了每种数占一种数的个数。

对于如何找到最小次数，我们发现，可以将它们占对方位置的行为看作一条有向边，互相占领的情况即形成了环。对于一个混乱的大小为 n 的环，将它恢复成有序需要 n-1 次交换操作，因此在得到上面的数据后，我们便可以通过找环来求解答案。

首先大小为 2 的环很容易找到，枚举 6 次找到 f_{i,j} 与 f_{j,i} 中的较小值即可。剩下环的大小均为 3 或 4，但简单手模就能发现，四种大小为 3 的环不可能同时存在，因为若同时存在，我们完全可以将它们重组成大小为 2 和 4 的环，而大小为 2 的环已经被找净了，所以不存在上述情况。这样一来，剩余环的数量即为剩下最多种类的数的数量，它存在于余下的所有环内。

实现

一些可能不易理解的操作标注了注释。

#include<bits/stdc++.h>
using namespace std;

const int Ratio=0;
const int N=2e5+5;
int n,ans;
int num[5],to[5][5];
struct rmm{int x,id;}a[N];
bool cmp(rmm a,rmm b){return a.x<b.x;}

namespace Wisadel
{
    short main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i,num[a[i].x]++;
        sort(a+1,a+1+n,cmp);
        // 按元素大小排序
        for(int i=1;i<=n;i++)
            if(a[i].id>=1&&a[i].id<=num[1]) to[a[i].x][1]++;
            else if(a[i].id>=num[1]+1&&a[i].id<=num[1]+num[2]) to[a[i].x][2]++;
            else if(a[i].id>=num[1]+num[2]+1&&a[i].id<=num[1]+num[2]+num[3]) to[a[i].x][3]++;
            else if(a[i].id>=num[1]+num[2]+num[3]+1) to[a[i].x][4]++;
        // 找到所占位置元素值，即连边
        for(int i=1;i<=4;i++) for(int j=i+1;j<=4;j++)
        {
            int sum=min(to[i][j],to[j][i]);
            ans+=sum,to[i][j]-=sum,to[j][i]-=sum;
        }// 找大小为 2 的环，直接交换
        int sum=0;
        for(int i=1;i<=4;i++)
        {
            int tot=0;
            for(int j=1;j<=4;j++)
                if(i!=j&&to[i][j]>0)
                    tot+=to[i][j];
            ans+=tot,sum=max(sum,tot);
            // 找环的数量
        }
        // 操作的最少次数即为 当前混乱的数的个数-环的数量
        printf("%d\n",ans-sum);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

完结撒花~