問題描述

有 n 個連續內存塊，k 個文件各自分為若干有序碎片存放。允許操作 a b：將內存塊 a 的內容移至空塊 b。目標：用最少操作使所有文件碎片按順序從最小編號塊開始連續存放。輸出操作序列。

核心觀察

• 每個碎片有「目標位置」，構成一個排列。
• 空塊是臨時緩衝區，利用空塊打破循環依賴。
• 貪心策略：優先將已在正確位置的碎片「固定」，再處理錯位碎片。

算法流程

1. 建立 flag[i] = j 表示位置 i 的碎片應去位置 j；0 表示空閒。
2. 階段一：掃描所有位置，若目標位置為空，直接移動並標記。
3. 階段二：若仍有錯位，選一個錯位碎片移至空閒位置（騰出新空位），回到階段一。
4. 重複直到所有碎片就位或判定無解（本題保證有解）。

代碼實現

#include <cstdio>
#include <cstring>
const int N = 10005;
int n, k, flag[N], num;

bool judge() {
    for (int i = 1; i <= num; ++i)
        if (flag[i] != i) return false;
    return true;
}

void solve() {
    int c = 0;
    while (true) {
        int cc = c;
        for (int i = 1; i <= num; ++i) {
            if (!flag[i]) { // 目標位置空閒
                for (int j = 1; j <= n; ++j)
                    if (flag[j] == i) {
                        printf("%d %d\n", j, i);
                        flag[i] = i; flag[j] = 0;
                        ++c; break;
                    }
            }
        }
        if (c == cc) break; // 本輪無移動
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        memset(flag, 0, sizeof(flag));
        num = 0;
        for (int i = 0; i < k; ++i) {
            int cnt, pos; scanf("%d", &cnt);
            while (cnt--) { scanf("%d", &pos); flag[pos] = ++num; }
        }
        if (judge()) puts("No optimization needed");
        else {
            solve();
            while (!judge()) {
                for (int i = 1; i <= num; ++i)
                    if (flag[i] && flag[i] != i) {
                        for (int j = num+1; j <= n; ++j)
                            if (!flag[j]) {
                                printf("%d %d\n", i, j);
                                flag[j] = flag[i]; flag[i] = 0; break;
                            }
                        break;
                    }
                solve();
            }
        }
        if (T) puts("");
    }
    return 0;
}

複雜度分析

• 時間：O(n²) 最壞情況，但 n ≤ 10000 且實際移動次數遠小於 n²，通過 UVA 時限。
• 空間：O(n)。

關鍵細節

1. num 統計碎片總數，只有前 num 個位置是目標區間。
2. 輸出格式：每組測試之間空行，無操作輸出 "No optimization needed"。
3. 移動後必須更新 flag 兩端：源置 0，目標置目標值。