Problem J47: Counting Out Game / 报数问题

版权信息： · 经典环形模拟（约瑟夫问题）

任务总览

题目描述

有 $N$ 个小孩围成一个圈，从 $1$ 开始依次编号。

现在规定：

• 从第 $W$ 个小孩开始报数；
• 报到第 $S$ 个数时，该小孩出列；
• 然后从下一个 小孩继续报数，依旧从 $1$ 报到 $S$；
• 重复该过程，直到所有小孩都出列。

请你输出小孩出列的顺序。

输入格式

*第一行一个整数 $N$（$1 \leq N \leq 64$），表示小孩数量；

• 接下来的 $N$ 行，每行一个字符串，表示一个小孩的名字（长度不超过 15 个字符）；
• 最后一行输入两个整数 $W$ 和 $S$，表示从第 $W$ 个小孩开始报数，每轮报到 $S$，中间用英文逗号 , 隔开。

输出格式

*输出 $N$ 行，每行一个小孩的名字，按照其出列的顺序排列。

输入输出样例

输入示例

5
Xiaoming
Xiaohua
Xiaowang
Zhangsan
Lisi
2, 3

输出示例

Zhangsan
Xiaohua
Xiaoming
Xiaowang
Lisi

题目分析与解法

✅ 解法思路（约瑟夫环问题）：

• 使用一个循环队列（如 vector 或 list）模拟小孩的环形站位；
• 从编号为 $W - 1$ 的小孩开始报数；
• 每次报到第 $S$ 个小孩将其移出，并记录出列顺序；
• 然后从其下一个小孩继续报数，循环进行，直到所有人都出列。

边界细节说明

*报数应为循环计数，超过当前人数时从头开始；

• 输入保证 $W < N$；

  • 名字可重复，程序以顺序为准，不考虑重名处理。

  ---

时间复杂度分析