#include<bits/stdc++.h> 
using namespace std;
long long n,k,ans,a[110000],b[110000],f[110000];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=b[i])
		{
			for(int j=i+1;j<=n;j++)
			{
				if(a[j]==b[i]&&a[i]==b[j])
				{
					swap(a[i],a[j]);
					ans++;
					break;
				}
				
			}
			if(a[i]!=b[i])	
			{
				f[a[i]]++;	
			}
		}
		
	}
	int t=min(f[1],min(f[2],f[3]));
		ans=ans+t*2;
		for(int i=1;i<=3;i++) f[i]-=t,k=k+f[i];
		ans=ans+k/2;
	cout<<ans;
}

贪心解决

#include <bits/stdc++.h>
using namespace std;
int n,a[1001],t[4],c[4][4],ans;
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i],t[a[i]]++;
    for (int i=1;i<=t[1];i++) c[1][a[i]]++;
    for (int i=t[1]+1;i<=t[1]+t[2];i++) c[2][a[i]]++;
    //统计个数
    ans=c[1][2]+c[1][3];//把1换到正确位置的最少步数
    c[2][3]+=max(0,c[2][1]-c[1][2]);//有多少3被交换到了二位置
    ans+=c[2][3];//将2,3交换到正确位置
    cout<<ans;
    return 0;
}