B. 凶险迷宫 详细题解

核心观察

1. 单元格 $i$ 距离出口的距离为 $\boldsymbol{n-i}$。
   • 数字越大，距离出口越近。
   • 出口是 $\boldsymbol{n}$，距离为 $0$。
2. 每个人必须使用传送器恰好 $k$ 次。
3. 要求 $\boldsymbol{a_i \neq i}$。
4. 我们的目标：让尽可能多的人最终停在最大的数字（即出口 $n$），使总距离最小。

构造策略（贪心）

我们只需要根据 $k$ 的奇偶性构造即可：

情况 1：$\boldsymbol{k}$ 是奇数（$k \% 2 = 1$）

• 目标：让所有人最终到达 $n$。
• 构造方式：
  • 前 $n-1$ 个位置：直接传送到 $\boldsymbol{n}$。
  • 第 $n$ 个位置：传送到 $\boldsymbol{n-1}$。
• 原理：
  • 位置 $1 \dots n-1$：$1$ 次传送直达 $n$，剩下 $k-1$（偶数）次在 $n$ 和 $n-1$ 之间来回跳，最终停在 $n$。
  • 位置 $n$：$1$ 次到 $n-1$，剩下偶数次来回，最终停在 $n$。

情况 2：$\boldsymbol{k}$ 是偶数（$k \% 2 = 0$）

• 目标：除了一个位置外，其余全部到达 $n$。
• 构造方式：
  • 前 $n-2$ 个位置：传送到 $\boldsymbol{n-1}$。
  • 第 $n-1$ 个位置：传送到 $\boldsymbol{n}$。
  • 第 $n$ 个位置：传送到 $\boldsymbol{n-1}$。
• 原理：
  • 位置 $1 \dots n-2$：偶数次传送后停在 $n$。
  • 位置 $n-1$ 和 $n$：偶数次来回后，一个在 $n$，一个在 $n-1$。
  • 这是满足 $a_i \neq i$ 约束下的最小距离和。

复杂度分析

• 时间复杂度：$\boldsymbol{O(n)}$ 每组测试用例。
• 空间复杂度：$\boldsymbol{O(1)}$。
• 完全满足 $n \le 2 \times 10^5$、$t \le 10^4$ 的数据范围。

总结

这是一道纯构造贪心题，核心就是：

• $k$ 奇：全员冲向 $n$。
• $k$ 偶：除一对来回点外，全员冲向 $n$。 按奇偶性直接输出对应数组即可。