uva 1016 - Silly Sort(置換+貪心)

uva 1016 - Silly Sort(置換+貪心)

題目鏈接：uva 1016 - Silly Sort

題目大意：給定一個長度為n的序列，每次操作可以交換任意兩個數的位置，代價為兩個數的和，求最小代價，將序列排成有序的。

解題思路：給定序列根據數的大小映射成一個置換，分解置換的循環，對於每個循環中，肯定是用值最小的逐個去交換的代價最小，但是要考慮，可以將最小的值與序列中最小值交換，用它代替去交換，最後再換回來。取兩種情況中最優的。

#include 
#include 
#include 

using namespace std;
const int maxn = 1005;

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

void init () {
    memset(v, 0, sizeof(v));
    memset(rec, -1, sizeof(rec));

    rep = maxn;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        pos[i] = arr[i];
        rep = min(arr[i], rep);
    }

    sort(pos, pos + n);
    for (int i = 0; i < n; i++)
        rec[pos[i]] = i;

    for (int i = 0; i < n; i++)
        pos[i] = rec[arr[i]];

    /*
    for (int i = 0; i < n; i++)
        printf("%d ", pos[i]);
    printf("\n");
    */
}

int solve () {
    int ret = 0;

    for (int i = 0; i < n; i++) {
        if (v[i])
            continue;

        int j = i, c= 0;
        int ans = 0, tmp = maxn;

        while (v[j] == 0) {
            tmp = min(tmp, arr[j]);
            ans += arr[j];

            v[j] = 1;
            c++;

            j = pos[j];
        }

        ans -= tmp;

        ret += ans + min(tmp * (c-1), tmp * 2 + rep * (c+1));
    }
    return ret;
}

int main () {
    int cas = 1;
    while (scanf("%d", &n) == 1 && n) {
        init();
        printf("Case %d: %d\n\n", cas++, solve());
    }
    return 0;
}