题解 P5462【X龙珠】

· · 题解

在我的博文中阅读以获得更好的阅读体验 。

Description

$n \leq 10^5

Solution

这是 洛谷7月月赛 的题目，因为比赛时间和上课时间刚好冲突于是就没有参加，所以在赛后来补题。

看到这道题目直接就一眼切掉了，但是因为细节问题导致我骗了一个数据点下了，还拿了一个题解来对拍（没看题解和题解代码）才过去的......

考虑使用 贪心 和 数组模拟链表 来接题。

因为要使字典序最大，所以我们要 让大的数尽量靠前 。但是显然当当前龙珠队列中剩下的最大的数在最后一个位置的时候，不能够达到 让大的数尽量靠前 ，为了方便表述，不妨设当前最大的数为 i ，它左边的数为 j （ i 没有右边的数 ）。

那么当j<(i-1)时，让(j+1) ~ (i-1)先放入目标队列是一个更优的选择。

于是我们就得到了一个很粗暴的做法：当 i 在最右边时，先跳过 i ，然后让去处理 (i-1) ，我们定义 p 为当前要处理的数。

那么当 p \leq 0 时检测一下是否所有数都到了目标队列即可，如果没有就让 p=n ，然后再做一遍即可，以此类推。

因为上述过程最多执行两次，所以时间复杂度是 O(n) 的，可以 A 掉本题。

注意要在中途检测 p 是否 \leq 0 。

具体的细节见 代码 。

Code

#include <cstdio>
int l[1000001],r[1000001];
int wz[1000001],a[1000001];
int main()
{
    int n=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        wz[a[i]]=i;
        l[i]=i-1,r[i]=i+1;
    }
    int p=0;
    while(true)
    {
        p=n;
        while(p>=1)
        {
            while(wz[p]==0)
            {
                p--;
                if(p<=0)
                {
                    break;
                }
            }
            if(p<=0)
            {
                break;
            }
            while(r[wz[p]]==n+1)
            {
                p--;
                if(p<=0)
                {
                    break;
                }
            }
            if(p<=0)
            {
                break;
            }
            while(wz[p]==0)
            {
                p--;
                if(p<=0)
                {
                    break;
                }
            }
            if(p<=0)
            {
                break;
            }
            int x=wz[p],y=r[wz[p]];
            printf("%d %d ",p,a[y]);
            int ta=l[x],tb=r[y];
            int dta=r[y],dtb=l[x];
            l[dta]=ta;
            r[dtb]=tb;
            wz[p]=wz[a[y]]=0;
            a[x]=a[y]=0;
        }
        bool flag=true;
        for(int i=1;i<=n;i++)
        {
            if(wz[i]!=0)
            {
                flag=false;
            }
        }
        if(flag==true)
        {
            break;
        }
    }
    return 0;
}