Question

给出一个 \(N\) 个元素的排序 \(a\)，我们可以对排列进行一些操作

• 将这个排列切割成若干个序列
• 将其中一些序列翻转
• 将这些序列连接起来得到一个新的排列

需要让最后的排列有序

Solution

这个题的描述有点小问题

理解应该是切一次，然后再反转合并，不可能会先合并再切再反转

然后考虑反转，如果一段序列是连续的，那么反转也是连续的

如果 \(a_i\) 和 \(a_{i+1}\) 的差值大于 \(1\) 那么仅仅靠反转操作是无法让序列边成有序的，所以这个地方必须切一刀

对于切割后的序列，通过多次反转和合并肯定能让序列保持有序

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int N,a[maxn],ans;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    N=read();
    for(int i=1;i<=N;i++){
        a[i]=read();
    }
    for(int i=1;i<N;i++){
        if(abs(a[i]-a[i+1])!=1) ans++;
    }
    printf("%d\n",ans);
    return 0;
}