自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:02，当前版本为作者最后更新于2022-05-21 16:40:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3630 排队顺序 題解

管理员注：

阅读本文章前，请先阅读$\ \texttt{ShanCreeper}$ B 题库题解的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】

点赞上文章即代表您已阅读并熟知其内容。

有 $n$ 个人，每个人只知道自己的身后是谁，已知第一位人的编号，输出整个排列顺序。

我们可以使用链表完成：

• 建立数组 $\texttt{nxt}$ 表示每个人身后人的编号；
• 定义 $\texttt{now}$ 表示当前指针，初始为 $\texttt{head}$；
• 如果 $\texttt{now}$ 不是 $0$ 时，输出 $\texttt{now}$，并将 $\texttt{now}$ 变为下一个指针位置。

比如数据：4 6 0 2 3 5。

我们可以先列一个表格。

假设队首为 1 号，则 $i$ 次循环 $\texttt{now}$ 和 $\texttt{nxt}_\texttt{now}$ 的值如下：

所以输出为：$1 \ 4 \ 2 \ 6 \ 5 \ 3$。

但是，如果不知道 $\texttt{head}$ 怎么办呢？

很简单，如果一个编号如果没有出现在任何一个人的后面，那么他就是第一个人。