sort3.cpp

USACO Section 2.1的全部AC的代码 OIer专用.

/*
NAME:lemon_c1
LANG:C++
PROG:sort3
*/
#include<fstream>
using namespace std;
ifstream cin("sort3.in");
ofstream cout("sort3.out");
int a[4];
int seq[1001];
int diff[4][4];
void swap(int &t1,int &t2)
{
	int t=t1;
	t1=t2;
	t2=t;
}
int main(void)
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>seq[i];
		a[seq[i]]++;
	}
	int st=0;
	int cnt=0;
	for(int k=1;k<4;k++)
	{
		for(int i=st;i<st+a[k];i++)
			if(seq[i]!=k)diff[k][seq[i]]++;
		st+=a[k];
	}
	int t1=min(diff[2][1],diff[1][2]);
	cnt+=t1;
	diff[2][1]-=t1;
	diff[1][2]-=t1;
	t1=min(diff[3][1],diff[1][3]);
	cnt+=t1;
	diff[3][1]-=t1;
	diff[1][3]-=t1;
	t1=min(diff[2][3],diff[3][2]);
	cnt+=t1;
	diff[2][3]-=t1;
	diff[3][2]-=t1;
	cnt+=max(max(max(diff[1][2],diff[1][3]),max(diff[2][1],diff[2][3])),max(diff[3][1],diff[3][2]))*2;
	cout<<cnt<<endl;
	return 0;
}