题意
从一个 $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;
}