OJ 題目「聰明的員工」演算法解析：最少移動次數讓隊伍順序符合目標

題目重述

有 n 位員工（2 ≤ n ≤ 30），初始排隊順序與目標順序皆為 1~n 的排列。每次操作只能將隊伍中的「某一位」員工移動到隊頭。求最少操作次數使初始順序變為目標順序。

範例分析

輸入：
4
2 1 3 4   // 初始順序
1 2 3 4   // 目標順序

輸出：1

解析：將員工 1 移到隊頭即可：[2,1,3,4] → [1,2,3,4]

核心觀察：逆向思維

關鍵洞察：從目標順序逆推，找出最長的「已經有序」尾部子序列。

• 操作「移到隊頭」相當於在目標序列中從後往前建立順序
• 目標序列中從右往左連續遞增的部分，在初始序列中相對順序已正確，無需移動
• 其餘元素皆需移動一次

演算法步驟

1. 建立位置映射：記錄每個員工編號在初始序列中的索引
2. 從目標序列右端開始向左掃描
3. 維護一個 prevPos 變數，初始為無限大
4. 若當前員工在初始序列中的位置 < prevPos，說明相對順序正確，更新 prevPos 並繼續
5. 否則中斷，已找到最長有序尾部
6. 答案 = n - 有序尾部長度

程式碼實作 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector init(n), target(n), pos(n+1);
        for (int i = 0; i < n; ++i) { cin >> init[i]; pos[init[i]] = i; }
        for (int i = 0; i < n; ++i) cin >> target[i];
        
        int prevPos = n;  // 初始設為超出範圍
        int orderedSuffix = 0;
        
        for (int i = n-1; i >= 0; --i) {
            if (pos[target[i]] < prevPos) {
                prevPos = pos[target[i]];
                orderedSuffix++;
            } else break;
        }
        cout << (n - orderedSuffix) << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n) 每測資
• 空間複雜度：O(n)
• n ≤ 30 非常小，任何 O(n²) 甚至 O(n!) 都能過，但 O(n) 最優雅

為什麼不是選擇排序？

原最佳回答給出的選擇排序程式碼完全錯誤，該題不是排序問題，而是在特定操作限制下的最小操作數問題。選擇排序的交換操作與「移到隊頭」本質不同，切勿混淆。

測試驗證

樣例 2：
3
2 1 3
3 1 2

初始位置：2→0, 1→1, 3→2
目標從右掃：2(pos=1<3)✓, 1(pos=1<1)✗ 中斷
有序尾部長度=1，答案=3-1=2 ✓