题解 P5462 【X龙珠】

题意描述

给你一个长为2n的珠子队列，每颗珠子的编号互不相同

要求取n次珠子，每次取相邻的2个

取掉后放到目标队列的末尾，并去除空隙

请你输出目标队列字典序最大的情况

解题思路

既然是互不相同

我们只用考虑每次去除的珠子中第一颗的大小
最后一颗珠子无法作为第一颗，因此需要特判

取出后去除间隙

用双向链表或vector实现
此题用双向链表更加简洁

每颗珠子的值不变

我们可以用静态的排序做
需要打标记

代码

#include <cstdio>
#include <algorithm>
int n,sum,v[100001],lst[100001],nxt[100001];
bool vis[100001];
struct hh{
    int x,id;
}a[100001];
int read(){
    char ch=getchar();int res=0,w=1;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {res=res*10+ch-'0';ch=getchar();}
    return res*w;
}
inline bool comp(const hh&x,const hh&y){
    return x.x>y.x;
}
int main(){
    n=read();
    for(register int i=1;i<=n;i++) {lst[i]=i-1;nxt[i]=i+1;v[i]=a[i].x=read();a[i].id=i;}
    std::sort(a+1,a+n+1,comp);
    for(register int i=1;i<n;i++)
        if(!vis[a[i].id]&&nxt[a[i].id]!=n+1)
        {
            printf("%d %d ",a[i].x,v[nxt[a[i].id]]);
            vis[a[i].id]=vis[nxt[a[i].id]]=true;
            nxt[lst[a[i].id]]=nxt[nxt[a[i].id]];
            lst[nxt[nxt[a[i].id]]]=lst[a[i].id];
            sum++;
            if(sum==n>>1) break;
        }
    puts("");
    return 0;
}