AT_abc337_c的题解

mgcjade · 2024-01-25 08:51:45 · 题解

AT_abc337_c的题解

题目大意

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

思考过程

从样例中不难发现：

• 输出序列中的每一个数均在 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;
}