uva 11330 - Andy's Shoes(置換)

uva 11330 - Andy's Shoes(置換)

題目鏈接：uva 11330 - Andy's Shoes

題目大意：小andy有很多鞋，穿完到處丟，後來他把所有鞋都放回鞋架排成一排，保證了鞋的左右交替，但是顏色混了。問說他至少移動多少次可以將鞋分類好。

解題思路：對應奇數位置為左鞋，偶數位置為右鞋，一雙鞋只有一只左鞋和一只右鞋，保證不換左變鞋子，以左鞋的位置為基准換右邊鞋子，對應右邊鞋子的位置即為一個置換，將置換的循環分解為x個互不相干的循環，ans=n-x

#include 
#include 
#include 

using namespace std;
const int maxn = 1e4+5;

int n, pos[maxn], v[maxn], arr[maxn];

int solve () {
    int ret = 0;
    memset(v, 0, sizeof(v));
    for (int i = 0; i < n; i++) {
        if (v[i])
            continue;

        ret++;

        int mv = i;
        while (v[mv] == 0) {
            v[mv] = 1;
            mv = arr[mv];
        }
    }
    return ret;
}

int main () {
    int cas, x;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &n);
        for (int i = 0; i < 2 * n; i++) {
            if (i&1)
                scanf("%d", &arr[i/2]);
            else {
                scanf("%d", &x);
                pos[x] = i/2;
            }
        }

        for (int i = 0; i < n; i++)
            arr[i] = pos[arr[i]];
        printf("%d\n", n - solve());
    }
    return 0;
}