题解 P5462 【X龙珠】

叫我DJ · 2019-07-14 19:17:27 · 题解

新鲜的题！！！

先用链表存储每一个编号的数前一个和后一个数的编号，最后由大到小枚举一遍，将没有用过的点连上后一个一起输出（注意它能输出，当且仅当它后面有数）

输出以后记得把它前一个数和它后面的后面的数连上

然后，就可以上代码了

#include <cstdio>

int n,a[100001],k[100001],x[100001],i;

int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d",&a[i]);
        k[a[i-1]]=a[i];
        x[a[i]]=a[i-1];}
    for(i=n;i>=1;--i)
        if(k[i])printf("%d %d ",i,k[i]),k[x[i]]=k[k[i]],x[k[x[i]]]=x[i],k[k[i]]=0;
    return 0;
}