📘 題意說明

畢業照拍攝時，老師希望隊伍能呈現左右對稱的樣子（即為「回文排列」）。
每次只能讓相鄰兩位同學交換位置，請問最少要幾次交換才能完成對稱排列。
若無論怎麼換都無法達成對稱，則輸出 Impossible。

🧠 解題核心思路

這題的核心是：

在只能相鄰交換的限制下，如何將一個數列變成回文，且花費的交換次數最少。

🔧 解法一：暴力模擬（會 TLE）

📝 方法說明

遍歷所有可能的交換方式，直到變成回文為止。
這種方式時間複雜度是 O(n²) 甚至更高，對於長度接近 10000 的資料會超時。

❌ 缺點

• 效能太差，無法通過大筆測資（TLE）

✅ 解法二：雙指針貪心法 + 模擬移動

📌 前置：先檢查是否能成為回文

1. 統計每個數字出現的次數

2. 若長度為 n 為偶數 → 每個數字出現次數都應為偶數
   若 n 為奇數 → 最多只能有一個數出現奇數次

3. 若不符合 → 輸出 Impossible

🧭 雙指針策略（Two Pointer）

1. 設定兩個指針：left = 0 和 right = n-1

2. 每次檢查 arr[left] 是否等於 arr[right]

   • ✅ 若相等 → 直接往中間靠近

   • ❌ 若不等 → 從右側往左找一個數 k 使 arr[k] == arr[left]

     • 若找到，就將 arr[k] 透過相鄰交換移動到 right

     • 若找不到，代表 arr[left] 是那個唯一出現奇數次的數 → 將它移動到中間

3. 每次交換時都計數，最後回傳總次數

⏱️ 時間複雜度分析

• 最多 n 次迴圈，每次最多移動 n 步

• 實際操作次數比 O(n²) 少，效能近似 O(n log n)，可以通過所有測資

🧠 小技巧補充

• 使用 STL 的 unordered_map 快速統計次數

• 若用 C++ 撰寫，可加上 ios::sync_with_stdio(false); 加速輸入

🏁 結論

這題結合了：

• 回文的基本判斷邏輯

• 雙指針貪心技巧

• 模擬相鄰交換過程

只要理解「每次儘可能讓兩側配對」的策略，就能有效減少交換次數，並順利通過所有測資。