P1996 约瑟夫问题
题目描述
\(n\) 个人围成一圈，从第一个人开始报数,数到 \(m\) 的人出列，再由下一个人重新从 \(1\) 开始报数，数到 \(m\) 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 \(n-1\) 名小朋友，而该题是全部出圈。
输入格式
输入两个整数 \(n,m\)。
输出格式
输出一行 \(n\) 个整数，按顺序输出每个出圈人的编号。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
\(1 \le m, n \le 100\)
📌 题目分析
给定数据：
要求按顺序输出依次出列的人的编号。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么“队列”是完美解法？
这道题最直观的动作就是“排队报数”。
遇到环形排队问题，C++ STL 中的 std::queue（队列）是终极杀器。
队列的特点是 “先进先出 (FIFO)”。我们可以利用它巧妙地模拟“围成一圈”的过程：
* 没数到 m 的人：从队头出来（出队），直接跑到队尾重新排队（入队）。这完美等价于环形中“报数但没被淘汰，轮到下一圈”的操作。
* 数到 m 的人：直接从队头出来（出队），被淘汰，不再回到队伍里，并打印他的编号。
2️⃣ 核心模拟逻辑
- 初始化：先把 \(1\) 到 \(n\) 这 \(n\) 个人的编号按顺序压入队列
q中。 - 开始报数：写一个
while (!q.empty())循环，只要队伍里还有人就不停。 - 循环数数：用一个
for循环从 \(1\) 数到 \(m-1\)。在这个过程中，把队头的人pop掉，并立刻push到队尾。 - 无情淘汰：循环结束后，现在的队头就是刚好数到 \(m\) 的人。打印他的编号，然后只
pop不push，他就永远地离开了这个圈。
3️⃣ 时间复杂度
队伍初始有 \(n\) 个人。每个人出列前，都需要经过 \(m-1\) 次的出队和入队操作。
在 \(n, m \le 100\) 的数据范围内，最多只需要 \(10000\) 次队列操作，对于 C++ 来说几乎是 \(0\) 毫秒的降维打击。
💻 C++代码
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 优化输入输出流
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
queue<int> q;
// 1. 初始化：所有人按顺序入队
for (int i = 1; i <= n; i++) {
q.push(i);
}
// 2. 模拟报数过程，直到队列为空
while (!q.empty()) {
// 让前面 m-1 个人安全过关，跑到队伍最后面去
for (int i = 1; i < m; i++) {
int safe_person = q.front();
q.pop();
q.push(safe_person);
}
// 现在的队头就是刚好报到 m 的人
int doomed_person = q.front();
cout << doomed_person << " "; // 打印被淘汰的人
q.pop(); // 彻底出队（不再 push 回去）
}
cout << "\n";
return 0;
}
⚠️ 易错点
❌ 1. 误用原生数组引发的低效
很多新手初学时喜欢开一个布尔数组 bool vis[105] 标记这个人是不是出列了，然后用一个死循环在数组里不停地转圈，数够了 \(m\) 个没被标记的人就改标记。
这种写法代码极度臃肿，且会有大量无意义的无效遍历（因为要反复跳过已经出列的人）。学会用 STL queue 可以把逻辑精简到极致。
❌ 2. 报数循环的边界问题
题目要求是“数到 \(m\) 的人出列”。
这意味着前面需要被转移到队尾的安全人数是 \(m-1\) 个人。所以内部的 for 循环条件必须是 i < m（或者 i = 1; i <= m - 1）。如果写成了 i <= m，就会错杀下一个人。
❌ 3. 忘记队列的头尾概念
在 queue 中，只能查看队头 q.front() 和队尾 q.back()。出队是 q.pop()，入队是 q.push()。千万不要和 vector 或者 stack 的方法搞混了（比如错写成 q.top()）。
🚀 一句话总结
🔥 补充：硬核知识点
约瑟夫问题的终极数学解法 (\(O(N)\) 递推)：
虽然这道题要求输出完整的过程，必须老老实实模拟。但如果题目变态一点，把 \(n\) 放大到 \(10^7\)，并且只问你最后一个幸存者是谁，用队列模拟绝对会 TLE（超时）。
这时候就需要用到图灵奖级别的数学公式了（动态规划推导）： 设 \(f(n, m)\) 表示 \(n\) 个人报数，数到 \(m\) 出列时，最后幸存者的编号（从 0 开始）。 它有一个极其优美的递推公式： $\(f(n, m) = (f(n-1, m) + m) \% n\)$ 边界条件：\(f(1, m) = 0\)（只有 1 个人时，幸存者下标肯定是 0）。
代码实现极短：
int survivor = 0; // f(1, m) 的情况
for (int i = 2; i <= n; i++) {
survivor = (survivor + m) % i;
}
// 最终答案加 1 转换回 1-indexed
cout << survivor + 1 << endl;