本文正體字版由OpenCC轉換

問題簡述

給定一個初始的排列P和M個輪換，每個輪換可以將排列P中的每個數值輪換爲排列中的另一個數值，輪換後仍然是一個排列。求出從排列P到排列1,2,3,…,N至少要經過多少次輪換，輸出一個方案。

問題分析

本題非常困難，好在是個提交答案題，可以看數據，然後針對每個數據設計合適的算法。不過在看數據之前，首先還是稍作一些轉換，以便簡化思維複雜度。本題中的“輪換”用了一種很彆扭的轉換方式（轉換數值），與以往的習慣格格不入（輪換位置），因此要把它轉化一下。用一個哈希表記錄每個數值的位置，形成新的排列Ti就表示原序列中數i在第Ti位，例如樣例中的4 3 1 2，轉化後就是3 4 1 2，在轉化後的序列上變換隻用變換位置即可，這樣就符合我們的習慣了（至少是我的習慣）。

接下來可以觀察數據了。首先發現測試點1、2、3的N、M都很小，可以直接搜索求解。用迭代加深或者廣搜即可拿到滿分。

觀察測試點4，N、M很大，沒辦法搜索了。但是發現所有輪換都是交換相鄰兩個元素，而且M=N-1，恰好囊括了N個元素所有相鄰兩對。這讓我聯想到冒泡排序的方法，由於冒泡排序每次交換的都是相鄰兩個元素，因此可以用來解決這個測試點。

測試點5的輸入文件是最大的一個，主要是由於M相當大，而且一時沒發現什麼規律。不過突然發現M=N*(N-1)/2，令我聯想到完全圖頂點和邊數的公式——是不是任意兩個都可以交換呢？寫程序判重以後發現果然是無重複的M個輪換，這意味着任意兩個位置可以交換。因此我們可以從1到N逐個確定每個位置上的值。

測試點6、7的共同特點是M=N-1，且每個輪換都是1和其他元素交換位置。判重後發現1和任意一個元素都能交換位置，對此我設計了一個貪心算法：每次把1上面的值換到目標位置上去，如果某時1恰好對應了1且還有元素沒有交換完成，則把下一個需要交換的元素與1交換，這種方法是的交換次數O(N)的。

測試點8、9、10都很大，但是明顯的共同特徵是M=N-1，一個不太明顯的特徵是所有輪換都是交換第i和i/2個元素。這個“不太明顯的特徵”恰恰是解決本題的關鍵，因爲如果抽象成圖，這是一棵完全二叉樹。可以看出每個位置上的值到目標位置只有唯一的路徑，這個路徑正是兩個點到最近公共祖先的路徑。於是方法就出來了，從第1個位置開始，找到i與T_i的最近公共祖先，經過這個路徑交換過去。

到此爲止已經解決了所有的測試點，回過頭來看看，發現除了前三個測試點以外，其餘所有的測試點中的輪換都是兩個元素的交換，如果看做圖論中一條邊的話，測試點描述了一個圖。再想想這個題爲什麼叫“排序機”？因爲每個測試的對應了一種排序方法。如下表所示：

至於這個題的一般方法，暫時還沒有好想法，仍需繼續研究、探討。

</>

[1]以一個點爲中心，其他所有點都是該點的子節點的樹。

上次修改時間 2017-05-22