AT3959 [AGC024B] Backfront 题解

题意

题目链接

从一个 $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;
} 
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇