765. Couples Holding Hands

Couples Holding Hands

題目描述： 有 n 對情侶坐在 2n 個座位上，我們想讓每對情侶都能坐在一起（相鄰的兩個座位）。每次操作可以選擇任意兩個人交換座位，求最少需要多少次交換。情侶的編號規則：(0,1)、(2,3)、(4,5)...即第 i 對情侶的編號為 (2i, 2i+1)。

解題思路：

1. 貪心策略：從左到右，每次檢查相鄰兩個座位上的人是否為一對情侶。如果不是，就找到當前位置的人的另一半，將其交換到正確位置。
2. 配對規則：對於編號 x，其配偶編號為 x ^ 1（異或 1）。偶數的配偶是下一個奇數，奇數的配偶是前一個偶數。
3. 正確性：每次交換至少能配對一對情侶，且不會打破已配對的情侶（因為我們從左到右處理），因此貪心是最優的。
4. 也可以用 Union-Find 來思考：每個錯配對形成一個環，環中 k 個錯配需要 k-1 次交換。

時間複雜度：O(n) — 遍歷一次座位陣列，每次交換為 O(1)

空間複雜度：O(n) — 用 pos 陣列記錄每個人的位置

1. Union-Find 方法：將每對座位看作一個節點，將每對情侶的實際座位連邊。連通分量中若有 k 對，需要 k-1 次交換。時間複雜度同為 O(n)，但概念上更直觀地解釋了最少交換次數的本質。

2. 環分解法：將錯位的配對關係建成置換圖，計算每個環的大小。一個大小為 k 的環需要 k-1 次交換來解開。這等價於 Union-Find 方法，但直接用 DFS 找環。

1. 如果不只是相鄰兩個座位要坐在一起，而是每 k 個人一組呢？如何推廣？
2. 如果交換有成本（例如距離越遠成本越高），如何求最小成本？
3. 能否用數學方法直接計算答案，而不需要模擬交換過程？