[USACO Section 2.1] Sorting a Three-Valued Sequence (求排序最少交换次数）

int a[maxn], n, b[5], sum = 0;
void change(int x, int y, int st1, int st2) {
    for (int i = st2; i < n; i++) if (a[i] == x) {
        while(a[st1] != y) st1++;
        if (st1 >= st2) break;
        swap(a[st1], a[i]);
        sum++;
    }
}
int main ()
{
    freopen ("sort3.in", "r", stdin);
    freopen ("sort3.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        b[a[i]]++;
    }
    change(1, 2, 0, b[1]);
//    cout<<sum<<endl;
    change(1, 3, 0, b[1]);
//    cout<<sum<<endl;
    change(2, 3, b[1], b[1] + b[2]);
    cout<<sum<<endl;
    return 0;
}

int a[maxn], part[4][4], n, b[4];
void get(int x, int st, int ed) {
    for (int i = st; i < ed; i++) {
        part[x][a[i]]++;
    }
}
int main () {
    freopen ("sort3.in", "r", stdin);
    freopen ("sort3.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        b[a[i]]++;
    }
    get(1, 0, b[1]);
    get(2, b[1], b[1] + b[2]);
    get(3, b[1] + b[2], n);
    int sum = 0, one_two = 0, one_three = 0, two_three = 0;
    one_two = min(part[1][2], part[2][1]);
    one_three = min(part[1][3], part[3][1]);
    two_three = min(part[2][3], part[3][2]);
//    for (int i = 1; i <= 3; i++, cout<<endl) {
//        for (int j = 1; j <= 3; j++)
//            cout<<part[i][j]<<" ";
//    }
    int tot = n - part[1][1] - part[2][2] - part[3][3];
    sum = one_two + one_three + two_three;
    sum = sum + (tot - sum * 2) / 3 * 2;
    cout<<sum<<endl;
    return 0;
}