问题简述

给定一个初始的排列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