AT3959 [AGC024B] Backfront 题解

发布于 2021-02-05  423 次阅读


题意

题目链接

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

月流华 岁遗沙 万古吴钩出玉匣