AcWing 1361. 三值序列排序
原题链接
中等
作者:
yls
,
2024-02-26 20:39:51
,
所有人可见
,
阅读 27
#include<iostream>
using namespace std;
const int N=1010;
int a[N],b[N],tong[4],e[N][N];
int m;
int main()
{
int n;
cin>>n;
for (int i = 0; i < n; i ++ )cin>>a[i],tong[a[i]]++;
for(int i=1,k=0;i<=3;i++)
for(int j=tong[i];j>0;j--)b[k++]=i;
for(int i=0;i<n;i++)e[a[i]][b[i]]++;//连边之后,肯定由一个个环组成,不是自环,就是大环,就是小环(自己想)
for(int i=1;i<=3;i++)m+=e[i][i];//自环也要加,因为m中的自环存在n(最终n个自环)中
for(int i=1;i<=2;i++)
for(int j=i+1;j<=3;j++){
int t=min(e[i][j],e[j][i]);//求小环,取min是公共小环,相当于交集
m+=t;
e[i][j]-=t,e[j][i]-=t;
}
m+=e[1][2]+e[2][1];//只剩大环,因为此时没有了不同时针序的大环,大环的个数相当于1和2之间边的个数(因为不确定时针方向,所以都加,肯定有一个值是0)
cout<<n-m;
return 0;
}