Solution Of P10522 雪中楼

Dr1fty · 2024-05-20 13:59:45 · 题解

Preface

简单题赛时做了 30+ 分钟，太菜了。

Solution

由于每次输入 a_i 我们会发现，在当前已经形成的序列中，i 比一直到 a_i 的高度都要大，因此在统计高度关系时要用到大量的插入操作，那么自然而然就想到了链表。

考虑维护一个链表 l，每次输入一个 a_i，若 i\neq 0 就把 i 插入到 l_{a_i} 的左边即可，否则插入到尾部。最后翻转即可。

如 \{0,0,0,0,2\}：

• 读入 a_1=0，将 i=1 插入到尾部，序列变成 \{1\}。
• 读入 a_2=0，将 i=2 插入到尾部，序列变成 \{1,2\}。
• 读入 a_3=0，将 i=3 插入到尾部，序列变成 \{1,2,3\}。
• 读入 a_4=0，将 i=4 插入到尾部，序列变成 \{1,2,3,4\}。
• 读入 a_5=2，将 i=5 插入到下标 2 的左边，序列变成 \{1,5,2,3,4\}。

最后翻转即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
list <int> q;
list <int> :: iterator 
    p[200005] = {q.begin(), q.begin()};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    for (int i=1, x; i<=n; i++)
        cin >> x, p[i] = q.insert(p[x], i);
    reverse (q.begin(), q.end());
    for (auto i : q) cout << i << ' ';
    return 0;
}