卢俊达

题目大意：

给定的一个1,2,3组成的数字序列，计算排成升序所需的最少交换次数。

思路：

挺简单的题但是思路不好叙述。

题目中给出序列 2 2 1 3 3 3 2 3 1 ，其升序为 1 1 2 2 2 3 3 3 3 。可以根据对比发现升序中属于1的位置上在原序列中有两个2，可以记作a_b=2。其他依次可以记作a_c=0，b_a=1，b_c=2，c_a=1，c_b=1。

第一步：首先考虑a_b与b_a，要实现升序，此处肯定会交换min(a_b,b_a)次。交换一次可以使两个数到达正确位置。b_c，c_b同理，所以这种情况一共交换min(a_b,b_a)+min(b_c,c_b)次。此时序列为 1 2 2 2 3 3 3 3 1 。

第二步：这时可以发现只剩a_b=1，b_c=1，c_a=1，只需交换两次即可，即把属于1位置上的2和属于3位置上的1交换，再把属于2位置的3和属于3位置的2交换。交换完后可以发现序列已经变为升序。

代码：

/*
ID: lujunda1
LANG: C++
PROG: sort3
*/
#include<iostream>
#include<stdio.h>
using namespace std;
int num[4]={0},arry[1000]={0};
//num[]用于记录序列中3个数字出现的次数。 
//arry[]存储序列。
int min(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	freopen("sort3.in","r",stdin);
	freopen("sort3.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&arry[i]);
		num[arry[i]]++;
	}
	int a_b=0,a_c=0,b_a=0,b_c=0,c_a=0,c_b=0;
	//a_b表示属于1的位置上出现2的次数。其他以此类推。 
	for(int i=0;i<n;i++)
		//通过循环对a_b、a_c等变量赋值。 
		if(i<num[1])
		{
			if(arry[i]==2)
				a_b++;
			else if(arry[i]==3)
				a_c++;
		}
		else if(num[1]<=i&&i<num[1]+num[2])
		{
			if(arry[i]==1)
				b_a++;
			else if(arry[i]==3)
				b_c++;
		}
		else if(num[1]+num[2]<=i&&i<n)
		{
			if(arry[i]==1)
				c_a++;
			else if(arry[i]==2)
				c_b++;
		}
	int sum=a_b+a_c+b_a+b_c+c_a+c_b,sub=min(a_b,b_a)+min(a_c,c_a)+min(b_c,c_b);
	//sub表示第一步所需的交换次数。 
	printf("%d\n",(sum-sub*2)/3*2+sub);
	//(sum-sub*2)/3*2表示第二步所需的交换次数。 
}

为了对应思路，使表述清晰，才有了上述的代码。但是从实现角度来看，上面的代码未免有些不太文艺。下面是简化后的代码，代码缩减近10行。

/*
ID: lujunda1
LANG: C++
PROG: sort3
*/
#include<iostream>
#include<stdio.h>
using namespace std;
int num[4]={0},arry[1000]={0},mark[4][4]={0};
//num[]用于记录序列中3个数字出现的次数。 
//arry[]存储序列。
//mark[i][j]表示属于i的位置上出现j的次数。 
int min(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	freopen("sort3.in","r",stdin);
	freopen("sort3.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&arry[i]);
		num[arry[i]]++;
	}
	for(int i=0;i<n;i++)
		if(i<num[1])
			mark[1][arry[i]]++;
		else if(num[1]<=i&&i<num[1]+num[2])
			mark[2][arry[i]]++;
		else
			mark[3][arry[i]]++;
	int sum=0,sub=0;
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			sum+=i-j?mark[i][j]:0;
	for(int i=2;i<=3;i++)
		for(int j=1;j<i;j++)
			sub+=min(mark[i][j],mark[j][i]);
	printf("%d\n",(sum-sub*2)/3*2+sub);
}