Solution

Permutation

题意简述：使用三种特定的操作完成对指定序列的排序操作

我们的答题思路是，采用类似于数学归纳的方法，先把前 $k$ 个数字排好序，然后把第 $k + 1$ 个数字排到最后面。我们要求每一次大的操作结束后，前 $k$ 个排好序的数字恰好位于后 $k$ 位。

下面来分情况讨论一下：

第一个数字的情形：

第一个数字恰好在当前序列的首位

直接翻转整个序列即可。

第一个数字不在当前序列的首位

直接一直做操作二直到第一个数字位于最后

第 2 至第 n - 2 个数字的情形：

假设已经排好了前 $k$ 个，现在要排第 $k + 1$ 个。

第 k + 1 个数字恰好位于当前序列的首位

这样的话我们的操作二没办法影响到第 $k + 1$ 个数字，所以要翻转序列。那么先做一次操作二，这样就能保证翻转以后，首位不会是前 $k$ 个数的其中一个，从而他们的相对顺序不会改变。然后做操作一，翻转序列。这时，容易发现，其实第 $k + 1$ 个数已经接在了前 $k$ 个数的后面，所以接下来只需要一直做操作二直到把第一个数丢到了结尾即可。然后再做一次操作二，再翻转回来就OK。

（这一段比较绕，读者可以自行在草稿纸上写写画画帮助自己理解）

第 $k + 1$ 个数字不在当前序列的首位

首先，把第 $k + 1$ 个数字丢到最后一位，然后翻转整个序列。这样的话，操作二就不会影响到第 $k + 1$ 个数字。然后，一直做操作二，直到第 $k$ 个数字被丢到了第二个位置，最后翻转整个序列即可。

最后两个数字的情形：

第 $n$ 个数字位于首位

直接做一次操作二，然后做一次操作三即可。

第 $n - 1$ 个数字位于首位

类似于上述第 $k + 1$ 个数字位于首位的情形，只是最后少做一次操作二。

复杂度分析の回合

容易发现，每一次把新的数接到原先排好序的序列的最后的过程，实际上最多做 $2n$ 次操作（事实上仔细分析应该是 $n+$ 常数级别，这里放的宽松一点显得我还像个人），而且操作三实际上最多用到一次（放到 $10$ 次是因为这样的话你的第一档部分分就可以用一些其他的方法水过去，具体怎么水过去留作读者练习）。

然而单次操作直接搞是 $O(N)$ 的，总复杂度可能达到 $O(N^3)$。然而可以使用带翻转标记的链表维护这个东东，可以实现 $O(1)$ 的单词操作，总复杂度降至 $O(N^2)$。具体实现留作读者练习。