Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

PROGRAM NAME: sort3

INPUT FORMAT

Line 1:	N (1 <= N <= 1000), the number of records to be sorted
Lines 2-N+1:	A single integer from the set {1, 2, 3}

SAMPLE INPUT (file sort3.in)

9
2
2
1
3
3
3
2
3
1

OUTPUT FORMAT

A single line containing the number of exchanges required

SAMPLE OUTPUT (file sort3.out)

4

这道题很神奇的贪心，第一章中讲贪心算法时讲过这个题的算法。

其实就是统计出1，2，3的个数，在1的位置上出现的2记为n12，在2位置上出现的1记为n21，如此。如果n12==n21，那么说明这两个位置上的数字只要一次交换就能得到最少的交换次数，如果其中某一个较大，那么较小的那个数就可以通过一次交换得到。其他位置同理。

把可以交换一次得到的个数都在各自中减去，那么剩下的序列必定每3个形如（3，2，1）的序列可以通过两次交换排序好，所以，对剩余的n(i,j)进行求和，再乘以2除以3，得到的数加到sum上即可……

我的语言描述真的很成问题……不说了，贴代码：

/*
ID:wangyuc2
PROG:sort3
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <memory.h>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin ("sort3.in");
ofstream fout ("sort3.out");  

int main()
{
    int a[1001];
    int nn[4]={0,0,0,0};
    int n13=0,n23=0,n12=0,n31=0,n32=0,n21=0;
    int i,sum=0,n;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
        nn[a[i]]++;
    }
    for(i=1;i<=nn[1];i++)
    {
        if(a[i]==2) n12++;
        if(a[i]==3) n13++;
    }
    for(i=nn[1]+1;i<=nn[1]+nn[2];i++)
    {
        if(a[i]== 1) n21++;
        if(a[i]== 3) n23++;
    }
    for(i=nn[1]+nn[2]+1;i<=n;i++)
    {
        if(a[i]== 1) n31++;
        if(a[i]== 2) n32++;
    }
    int t;
    if(fabs(n12-n21)) {t=n12>n21?n21:n12; n21-=t;n12-=t;sum+=t;}
    else{t=n12;n12=0;n21=0;sum+=t;}
    if(fabs(n13-n31)) {t=n13>n31?n31:n13; n31-=t;n13-=t;sum+=t;}
    else{t=n13;n13=0;n31=0;sum+=t;}
    if(fabs(n32-n23)) {t=n32>n23?n23:n32; n23-=t;n32-=t;sum+=t;}
    else{t=n32;n32=0;n23=0;sum+=t;}
    sum+=(n12+n21+n13+n31+n23+n32)*2/3;
    fout<<sum<<endl;
   // system("PAUSE");
    return 0;
}

运行结果如下：

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2844 KB]
   Test 2: TEST OK [0.011 secs, 2844 KB]
   Test 3: TEST OK [0.000 secs, 2840 KB]
   Test 4: TEST OK [0.011 secs, 2844 KB]
   Test 5: TEST OK [0.011 secs, 2840 KB]
   Test 6: TEST OK [0.011 secs, 2840 KB]
   Test 7: TEST OK [0.011 secs, 2840 KB]
   Test 8: TEST OK [0.011 secs, 2844 KB]

All tests OK.

YOUR PROGRAM ('sort3') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.