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

ZBXAZYZ1 · 2025-07-26 21:29:34 · 题解

前言：这道题目的数据真的很水。

进入正题：

一.我们怎么确定这道题是什么算法?

我们可以先看 100\% 的数据：

对于 100\% 的数据，1 \le n \le 10^{5} ，保证 p 是一个 1 \sim n 的排列。

由此，我们可知暴力是会超时的，通过此题要用 O(n) 或 O(n \log n) 的做法，考虑数学或二分。但这道题不满足使用二分的单调性，所以这道题我们使用数学。

二.如何得出规律?

我们可以针对样例：

对于样例一的解释：这明显是一个连续上升的序列，不用交换，所以 k 为 1。同样的，只要序列满足连续上升，则 k 为 1。

对于样例二的解释：这个序列有两个依次上升的子序列，我们可以交换这两个子序列，使它变得有序，所以 k 的值为 2。同样的，序列只要满足有两个依次上升的子序列，我们的 k 就等于 2。（注：这两个序列一定是依次上升的，否则就不能输出 2。）

对于样例三的解释：对于这个完全无序的序列，我们可以输出 3，可以证明 3 是最小的 k，我们只需要每次将最大值、次大值、次次大值......依次找出来，将它的左边变成序列一，本身变成序列二，右边变成序列三，将序列一和序列二交换，就可以将最大值、次大值、次次大值......依次放在序列的左边，也就是说，对于一个长度为 n 的完全无序的序列，最多进行 n 次操作，就可以将它变成一个有序的序列，以下是例子：

对于序列：3、2、4、1，我们可以很容易发现它是完全无序的，我们可以做出以下操作：

1. 交换 3、2 和 4 得序列 4、3、2、1。

2. 交换 4 和 3 得序列 3、4、2、1。

3. 交换 3、4 和 2 得序列 2、3、4、1。

4. 交换 2、3、4 和 1 得序列 1、2、3、4。

综上，我们的 k 最小是 3。

三.代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],l;
bool check(int r){//判断 k 是否是 1 或 2。
    for(int i=r;i<n;i++){
        if(a[i]!=a[i+1]-1){
            return 0;
        }
    }
    for(int i=1;i<r-1;i++){
        if(a[i]!=a[i+1]-1){
            return 0;
        }
    }
  //以上是遍历序列，看看它是否满足样例二的格式。
    return 1;//满足返回 1。
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1){
            l=i;//记录 1 的位置，遍历的时候有一个起始点。
        }
    }
    if(check(l)&&l==1){//特判，如果它是样例一的格式，输出 1。
        cout<<1;
    }
    else if(check(l)){//否则如果它满足有两个依次上升的子序列，输出 2。
        cout<<2;
    }
    else{//如果它是完全无序的序列，输出 3。
        cout<<3;
    }
    return 0;
}