题解：P10522 [XJTUPC2024] 雪中楼

dingYKP · 2024-05-21 16:39:39 · 题解

维护一个链表 d，编号为 d_i 的楼的高度高于编号为 d_{i+1} 的楼的高度。

对于每一次观察，有两种情况：
若 a_i 为 0，由题意知当前楼的高度为最矮的，将当前楼加入到链表尾部。
若 a_i 不为 0，说明当前楼高度比编号为 a_i 的楼高且在所有高度高于 a_i 的楼中，当前楼是最矮的。故在 d 中将当前楼插入到 a_i 之前。

最后将 d 倒序输出即可。

Code

#include <iostream>
using namespace std;
int pre[200010],nxt[200010];
int main(){
    int n,f=1,l=1;//f代表当前高度最高的楼编号，l代表最低的楼编号
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        if(t==0){
            pre[i]=l;
            nxt[l]=i;
            l=i;
        }
        else{
            if(pre[t]==0){
                f=i;
                nxt[i]=t;
            }
            else{
                nxt[pre[t]]=i;
                pre[i]=pre[t];
                pre[t]=i;
                nxt[i]=t;
            }
        }
    }
    int cur=l;//当前输出的楼编号
    for(int i=0;i<n;i++){
        cout<<cur<<" ";
        cur=pre[cur];
    }
}