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

SAMPLE INPUT (file sort3.in)

9
2
2
1
3
3
3
2
3
1

OUTPUT FORMAT

SAMPLE OUTPUT (file sort3.out)

4

题意：对所有的“1”， “2', "3"按非降排序，并求出最小交换次数

/**//*
LANG: C
TASK: sort3
*/
#include<stdio.h>
#define nmax 1001
int bucket[4][4], len[4], nswap;
void SetLen()
{
    int i, j;
    for (i = 0; i <= 3; i++)
    {
        len[i] = 0;
    }
    for (i = 1; i < 4; i++)
    {
        for (j = 1; j < 4; j++)
        {
            bucket[i][j] = 0;
        }
    }
}
void swap(int i, int j)//将每两个桶中能互相交换的盘子个数，这样就求出了一些交换次数。 
{
    if (bucket[i][j] < bucket[j][i])
    {
        nswap += bucket[i][j];
        bucket[j][i] -= bucket[i][j];
        bucket[i][j] = 0;
    }
    else
    {
        nswap += bucket[j][i];
        bucket[i][j] -= bucket[j][i];
        bucket[j][i] = 0;
    }
}
int main()
{
    int i, j, k, sum, s[nmax],  t, n, temp, time;
    freopen("sort3.in", "r", stdin);
    freopen("sort3.out", "w", stdout);
    scanf("%d", &n);
    SetLen(n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &k);
        s[i] = k;
        len[k]++;//求出每个数字出现得个数，即求排好序后装数字k的桶容量 
    }
    k = 0;
    for (i = 1; i <= 3; i++)
    {
        for (j = k, k += len[i]; j < k; j++)
        {
            bucket[i][s[j]]++;//计算现在桶i里每种盘的个数 
        }
    }
    nswap = 0;
    swap(1, 2);
    swap(1, 3);
    swap(2, 3);
    sum = 0;
    for (i = 1; i < 4; i++)//对任意两个桶中不能直接交换的盘子，让三个桶轮流交换 
    {
        for (j = 1; j < 4; j++)
        {
            if (i != j)
            {
                sum += bucket[i][j];
            }
        }
    }
    nswap += sum / 3 * 2; 
    printf("%d\n", nswap);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
/**//*
20 
1 
1 
3 
2 
1 
1 
1 
3 
2 
1 
3 
3 
2 
1 
3 
1 
1 
2 
3 
1 
*/