AT_abc337_c的题解

题目大意

就是给你一个数组 $a=(a_1,a_2,\ldots,a_n)$，若 $a_i$ 为 $-1$，那么这个数的下标就是输出序列的开头，否侧，这个数在输出序列中排在 $a_i$ 的下一个。

思考过程

从样例中不难发现：

• $1,2,\ldots,n$ 中的每一个数最多在 $a$ 中出现一次；

• 输出序列中的每一个数均在 $1,2,\ldots,n$ 之间并且会且仅会出现一次。

考虑使用链表。那么链表中的第一个数就是 $a_i$ 中为 $-1$ 的那一个数，每一个数的后继 $j$ 就是 $a_j$ 为 $i$ 的数。

Code

码风较丑勿喷

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;

int n;
int a[N];
int nxt[N];

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);

        if (a[i] == -1)
            nxt[0] = i;
        else
            nxt[a[i]] = i;
    }

    for (int i = nxt[0]; i; i = nxt[i])
        printf("%d ", i);

    return 0;
}