题解：P13492 【MX-X14-T2】反转时光

· · 题解

题目大意

题目和样例解释的比较清楚，不再过多解释。

分析

看到这题时我先找原序列中已经排好序部分的长度，最后再用总长减去这部分的长度再加一得到答案。但很显然，这样是错的，并且只能得 55 分。

但后来我突然意识到这可能是一道结论题，最大的答案不超过 3。其中，1 的情况就是原序列已经排好序，不需要再做出更改。2 的情况就是例如 [4 , 5 , 6 , 1 , 2 , 3] 这样，证明起来也十分简单。而最重要的时当答案为 3 时，该如何证明？经过了半天的思考，我得出了一种做法：给定一个序列 [4 , 7 , 2 , 3 , 6 , 1 , 5]。我们先把它划分为 [4],[],[7 , 2 , 3 , 6 , 1 , 5]，然后交换，变成 [7 , 2 , 2 , 6 , 1 , 5 , 4]。再划分为 [7],[2 , 3 , 6 , 1 , 5],[4]，交换为 [7 , 7 , 2 , 3 , 6 , 1 , 5]