AT_arc181_a Sort Left and Right 题解

2024/08/11 Blog

赛时糖丸了,吃了 $5$ 发罚时才过。

解法

如果输入序列有序则答案一定为 $0$,这里不多讨论。

可以发现把序列还原可以通过两种方法,一种是在 $1$ 或者是 $n$ 已经还原的情况下通过 $1$ 步使整个序列还原,还有一种是通过选取一个在中间的和左右两边都不产生逆序对的数使序列还原。其实不难发现第一种方法是第二种方法的特殊情况。

第二种方法显然只能用一次,否则一定不会比第一种方法更优。

考虑第一种方法,如果 $1$ 或 $n$ 已经还原的话答案是 $1$。否则我们需要把 $1$ 或 $n$ 还原。

考虑极端情况,就是 $a_1 = n,a_n = 1$,那最少需要两步才能使 $1$ 或 $n$ 还原,所以答案是 $3$。

剩下的情况答案是 $2$,即通过 $1$ 步使 $1$ 或 $n$ 还原,然后通过 $1$ 一步使序列还原。

代码

#include<bits/stdc++.h>
namespace fast_IO
{
    /**
     * useless fast IO
    */
};
using namespace fast_IO;
int t,n,a[200010],maxi[200010],mini[200010];
bool flag;
int main()
{
    in>>t;
    while(t--)
    {
        in>>n,flag=1;
        for(int i=1;i<=n;i++) in>>a[i],flag&=(a[i]==i);
        if(flag)
        {
            out<<"0\n";
            continue;
        }
        maxi[0]=INT_MIN,mini[n+1]=INT_MAX;
        for(int i=1;i<=n;i++) maxi[i]=std::max(maxi[i-1],a[i]);
        for(int i=n;i;i--) mini[i]=std::min(mini[i+1],a[i]);
        for(int i=1;i<=n;i++) if(maxi[i-1]<=a[i] && mini[i+1]>=a[i]) flag=1;
        if(flag) out<<"1\n";
        else if(a[1]==n && a[n]==1) out<<"3\n";
        else out<<"2\n";
    }
    fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
    return 0;
}
对我博客最大的鼓励来自于你的评论(什么玩梗),欢迎选择 来回复, 也可以在 GitHub discussion 留言。

Search

    公告

    博主这下真摆烂了。我下辈子也不碰 Jekyll 和 MathJax 了!
    留言板,现在博主的精神状态非常好,有事烧纸。

    联系方式

    QQ: 33299235
    email: 33299235@qq.com
    Gmail: scp020.cn@gmail.com

    本人的其它个人主页

    洛谷
    CSDN

    友链

    拜谢stevehim(已退役,祝好)
    拜谢日记
    拜谢cppomstar

    views counting

    Document

    Table of Contents