学习目标

• 用队列轮转模拟循环报数，输出完整出列顺序。
• 明确每轮从当前队头报 1，出列后从下一人重新报 1。
• 分析队列轮转的最坏时间与空间。

前置知识与环境

建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。

任务

编号 1..n 的人按编号围成一圈，最初从编号 1 开始报 1；报到 k 的人出列，下一轮从刚出列者之后尚在圈中的人重新报 1。每轮可把前 k-1 人依次从队头转至队尾，再让队头出列。

输入格式

一行两个正整数 n k，报数步长为 k。

输出格式

输出完整出列顺序，各编号以空格分隔，末尾换行。例如 7 3 的顺序为 3 6 2 7 5 1 4；k=1 时顺序为 1..n。

数据范围与限制

• 除题面另有说明外整数使用 64 位有符号范围。
• 1 <= n <= 5000 且 1 <= k <= 5000；报数从当前队头开始，数到 k 的元素出列，下一轮从其后一个元素继续。
• 本题的循环队列模拟允许 O(nk) 最坏时间，辅助空间为 O(n)。
• 标准输出只保留题目要求的结果；调试信息写入标准错误。
• 目标算法应符合本题给出的 O(nk) 循环队列模拟要求。

边界与验收重点

• 单人、k=1、k=n 和 k>n。
• 每次出列后队头必须是刚出列者之后的下一位存活者。
• 本题输出完整过程，不只输出最终幸存者。

如何验证

make doctor
make run
make score

未安装 Make 时，在仓库根目录运行：

pnpm lab:validate -- labs/chapter-02/exercise/E-02-15-josephus-order
pnpm lab:run -- labs/chapter-02/exercise/E-02-15-josephus-order
pnpm lab:score -- labs/chapter-02/exercise/E-02-15-josephus-order

• 全部 20 个公开测试通过。
• 能手算 7 3 的前两轮 3、6。
• 能解释轮转实现的 O(nk) 时间和 O(n) 空间。

思考与复盘

1. 为什么 k=1 时不需要轮转队列？
2. 若每轮都从编号 1 重新开始，会在哪一步与样例不同？

思考题参考

1. 当前队头就是本轮报 1 的人，应立即出列。
2. 编号 3 出列后应从 4 报 1，下一位出列者是 6，而不是重新从 1 计数。

题解

点击查看题解

思路与不变量

队列从队头开始表示当前仍在圈中的人，队头就是本轮报 1 的人。每轮把前 k-1 人移到队尾，随后删除队头；删除后新的队头自然是下一轮报 1 的人。

算法步骤

1. 将 1..n 依次入队；
2. 队列非空时循环 k-1 次完成轮转；
3. 输出并弹出队头；
4. 重复直到队列为空。

正确性说明

轮转后队头正好是从当前报数起第 k 个人，因此删除它符合规则；被删除者之后的存活者成为新的队头，满足下一轮从其后重新报 1。每轮都保持队列按圈中顺序排列，所以输出完整且顺序正确。

复杂度分析

• 时间复杂度：O(nk)，每轮最多移动 k-1 人；
• 额外空间：O(n)，队列保存尚未出列的人。

边界注意

• k=1 时不需要轮转，直接依次出队；
• k 可能大于当前队列长度，仍按题目定义执行 k-1 次轮转；
• 输出的是完整出列顺序，不是只保留最后一个人的经典 Josephus 结果。