题意

题目链接

从一个 $1\sim n$ 的排列中不断选择元素放在头或尾，最终使其有序，询问操作次数。

解析

首先容易发现，至多操作 $n$ 次一定能够使其有序（一个一个拎出最小的或最大的）。

然后我们发现，$n$ 次可以变为 $n-1$ 次，我们先随意确定一个数，比它小的按顺序拎到它左边，后边亦然。

接着我们考虑，能否从确定一个数变为确定一个序列呢？显然，如果有一段序列，其数字是严格一个一个递增的，位置也是递增的（例如：$1,4,2,5,6,3$ 中的 $1,2,3$）。我们可以永远不选择这些数，而按照前面所叙述的原则将其他数按顺序拎到左边或右边即可，答案即为这个最长递增子序列的长度。

那么怎么求呢？只需要把每一个数字对应的位置记录下来，然后按数字大小遍历并判断是否大于前一个即可，详见代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N],b[N];
int ans,tmp;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[a[i]]=i;//记录位置 
    }
    tmp=ans=1;
    for(int i=2;i<=n;i++){//寻找最长递增子序列 
        if(b[i]>b[i-1]){//如果连续的几个数，位置递增，显然是一个递增子序列 
            tmp++;
            ans=max(ans,tmp);
        }
        else tmp=1;
    }
    printf("%d\n",n-ans);
    return 0;
}