题目大意：
给定的一个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
#include
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
#include
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);
}