sort3.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: sort3
LANG: C++
*/
#include <stdio.h>


int counts[4][4]={0};
int num[4]={0};
int nums[1001];
int N;
#define MIN(A,B) (A<B?A:B)
int main()
{
	freopen("sort3.in","r",stdin);
	freopen("sort3.out","w",stdout);
	scanf("%d",&N);
	for(int a=1;a<=N;a++)
	{
		scanf("%d",&nums[a]);
		num[nums[a]]++;
	}
	for(int a=1;a<=N;a++)
	{
		if(a<=num[1])
			counts[nums[a]][1]++;
		else if(a>num[1]&&a<=num[1]+num[2])
			counts[nums[a]][2]++;
		else
			counts[nums[a]][3]++;
	}
	int answer=0;
	int m1=MIN(counts[1][2],counts[2][1]);
	int m2=MIN(counts[1][3],counts[3][1]);
	int m3=MIN(counts[2][3],counts[3][2]);
	counts[1][2]-=m1;
	counts[2][1]-=m1;
	counts[1][3]-=m2;
	counts[3][1]-=m2;
	counts[2][3]-=m3;
	counts[3][2]-=m3;
	for(int a=1;a<=3;a++)
		for(int b=1;b<=3;b++)
			if(a!=b)
				answer+=counts[a][b];
	answer=answer*2/3;
	answer+=m1+m2+m3;
	printf("%d\n",answer);
	return 0;
}