WC2010 排序機

問題簡述

給定一個初始的排列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與Ti的最近公共祖先,經過這個路徑交換過去。

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

測試點 圖論結構 排序方法
4 冒泡排序
5 完全圖 選擇排序
6,7 蜘蛛型樹[1] 選擇排序
8,9,10 完全二叉樹 堆排序

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

</>

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

相關日誌