问题标题: 酷町堂：2639 三值排序

说到三值排序，就必须要讲到二值排序。

二值排序就是找到“1”和“2”的分界线，也就是“1”的个数。然后从分界线的两边进行寻找，交换，计数，做后输出结果。

三值排序和二值排序有点相似，不过有两条分界线，分别是“1”和“2”的分界线，也就是“1”的个数；还有“2”和“3”的分界线，也就是“1”和“2”的个数相加。这一步可以在输入中实现。

    int n,a[10010],n12=0,n13=0,n21=0,n23=0,n31=0,n32=0,x=0,y=0,z=0;
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        if(a[i]==1) x++; //“1”的个数
        else if(a[i]==2) y++;//“2”的个数
        else z++; //“3”的个数
    }

然后在“1”的区域里（1~x）寻找“2”和“3”，在“2”的区域（x+1~y）里寻找“1”和“2”，在“3”的区域（x+y+1~n）里寻找“1”和“2”，分别统计。

    for(int i=1;i<=x;i++) //在“1”的区域里找“2”和“3”。
    {
        if(a[i]==2) n12++;
        else if(a[i]==3) n13++; 
    }
    for(int i=x+1;i<=x+y;i++) //在“2”的区域里找“1”和“3”。
    {
        if(a[i]==1) n21++;
        else if(a[i]==3) n23++; 
    }
    for(int i=x+y+1;i<=n;i++) //在“3”的区域里找“1”和“2”。
    {
        if(a[i]==1) n31++;
        else if(a[i]==2) n32++; 
    }

现在，开始计数。

    在交换数时只有两种情况：

（1）交换一次两个数都能回到正确的位置上。

                例如“2”区域里的“3”和“3”区域里的“2”交换，“2”回到了“2”的区域，“3”也回到了“3”的区域。

                这时，我们能一下子交换两个数的个数，在于较小的那个个数。比如“1”区域里有三个“2”，但是“2”区域里只   

                有 一 个“1”，所以，在“1”区域和“2”区域中能一下交换后，两个数都能回到正确的位置上的个数，只能是较小的那 

                个数，也就是只能交换一个。

    long long sum=0;
    sum+=min(n12,n21)+min(n13,n31)+min(n23,n32);

（2）交换时只能使一个数回到正确的位置上。

                例如“3”区域里的“2”和“1”区域里的“3”交换，只有一个“3”回到了正确的位置上。

                多观察几次，就可以得到这样的一个结论：每这种情况下的三个数都需要两次。

                所以，我们只需要把一共需要交换的数，减去上一种情况所交换完的数（由于上一种情况交换一次两个数都回到正确位置， 

                所以是sum*2），然后*3/2就行了！

sum+=(n12+n13+n21+n23+n31+n32-sum*2)/3*2;

最后输出sum，就AC了！！！

祝你AC快乐！！！