上次那篇日志发布之后，据说大家解题的热情相当高。Michael Brand告诉我说，他收到了很多来自中国的邮件，他感到非常高兴。在揭晓谜底之前，还是让我们先回顾一下题目：

    对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方（说穿了就是一次选择剪切粘贴的操作）。例如，数列1,4,5,6,2,3,7可以通过一次块移动完成排序（把456挪到3后面）。那么，想要让一个1到n的逆序排列n, n-1, …, 3, 2, 1变为顺序排列，最少需要多少次块移动？给出你的算法，并证明这个移动数目不能再少了。

    需要指出的是，答案并不是n-1那么简单。当n=5时，只需要三步就可以搞定了：

 5  4 [3  2] 1
 3  2  5 [4  1]
[3  4] 1  2  5
 1  2  3  4  5

    事实上，给出1到n的逆序排列，最少需要Ceil[(n+1)/2]次块移动就可以完成排序（除了n=1或n=2，Ceil表示取上整）。当n为奇数时，一个满足要求的算法是：每一次把数字n后面那一段的正中间两个元素拿出来，插入到数字n前面那一段数的正中间。当数字n后面的数被移动完了后，把它前面n-1个数左右两半对换一下就行了。例如，当n=7时：

 7  6  5 [4  3] 2  1
 4  3  7  6 [5  2] 1
 4  5  2  3  7 [6  1]
[4  5  6] 1  2  3  7
 1  2  3  4  5  6  7

    算法的移动步数显然为(n+1)/2，其正确性可以用数学归纳法说明，这里不再详细叙述了。
    当n为偶数时，只需要用n/2次操作把前面n-1个元素排好序，再花一次操作把末一个元素移动到最前面，加起来正好Ceil[(n+1)/2]次操作。下面我们证明，移动次数不可能比Ceil[(n+1)/2]更少。
    对于数列中相邻的两个数，如果前面那个数比后面的大，我们就把它们俩称作一组“逆序相邻数”。初始时，数列中有n-1个这样的逆序相邻数，我们的目标就是通过块移动把这个数目减少到0。整个证明过程的关键就在于，一次块移动操作最多只能消除两个逆序相邻数。

原数列： **aA–Bb***CD****
新数列： **ab***CA–BD****

    假如我们把块A–B插入到CD中间。注意到，相邻数发生变动的地方只有三处。要想同时消除三个逆序相邻数，只有一种可能：原数列中a>A, B>b, C>D，同时新数列中的a<b, C<A, B<D。这将导出一个很荒谬的结论：A < a < b < B < D < C < A。这告诉我们，一次块移动同时消除三个逆序相邻数是不可能的，它最多只能消除两个逆序相邻数。另外，容易看出，第一次移动只能消除一个逆序的相邻数，因为初始时原数列完全逆序，即有a > A > B > b > C > D，在新数列中只有C<A成立。对称地，最后一次移动也只可能消除一个逆序相邻数，因为新数列中a < b < C < A < B < D，只有B>b是成立的。
    于是我们得知，k次块移动最多消除1+2*(k-2)+1个逆序相邻数。为了消除n-1个逆序相邻数，我们有1+2*(k-2)+1 >= n-1，整理得k>=(n+1)/2。

 
题目来源：http://www.brand.site.co.il/riddles/200809q.html