[USACO][Section 2.1][排序] Sorting a Three-Valued Sequence

题目大意：

给定的一个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
为了对应思路，使表述清晰，才有了上述的代码。但是从实现角度来看，上面的代码未免有些不太文艺。下面是简化后的代码，代码缩减近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