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]以一个点为中心,其他所有点都是该点的子节点的树。

相关日志