题解 P5462 【X龙珠】

· · 题解

思路：

看到好多人用贪心+排序或者一个链表过了

我太弱了

只能想到堆+链表的辣鸡做法

其实这种方法挺套路化的

每次贪心的选择编号最大的元素

然后在堆里删掉他自己和他后面的元素

然后用链表维护每个元素的前驱后继关系

注意：队尾的元素是不能成为选择对象的，否则就会把后面的0一起拉出来

如 1 2 3 4

第一次就会把4和后面的0拉出来

由于队尾只能通过他的前驱拉出来

所以不入堆不会影响答案

直接特判掉pop即可

代码：

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
inline int read(){
    int x;scanf("%d",&x);return x;
}
struct node{
    int id,val;
};
inline bool operator<(const node &a,const node& b){
    return a.val <b.val;
}
priority_queue <node> Q;
const int N =1e6;
int a[N],pre[N],nxt[N],ans[N],sz,vis[N],n;
//同时维护一个堆和链表
int main(){
    n =read();
    for(int i=1;i<=n;++i){
        pre[i] =i-1;
        nxt[i] =i+1;
        a[i] =read();
        if(i!=n)    Q.push(node{i,a[i]});
    }//队尾元素不能入堆

    for(;;){
        while((vis[Q.top().id]||nxt[Q.top().id]>n) && Q.size()) Q.pop();    //懒标记删除法，注意特判掉队尾
        if(Q.empty())   break;
        node x =Q.top();    Q.pop();
        int val =x.val,u =x.id,v =nxt[u];
        ans[++sz] =val;
        ans[++sz] =a[v];
        vis[u] =true;
        vis[v] =true;
        nxt[pre[u]] =nxt[v];
        pre[nxt[v]] =pre[u];    //链表的删除操作
    }
    for(int i=1;i<=n;++i)   printf("%d ",ans[i]);
}