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 
*/