题解：P1996 约瑟夫问题
interesting_soul_zjy
·
·
题解
题解：P1996 约瑟夫问题
题意
## 分析
本题我们可以用 STL 中的队列解决。队列是一种先进先出的数据结构，从最后面的队尾插入，从最前面的队首弹出。
可以先将 $1$ 到 $n$ 插入队列，如果队列里还有元素，就弹出队首元素。如果判断到这时正好报到 $m$，直接输出编号，否则再将它插入队列。因为每循环 $m$ 次才能使一个人出圈，所以使 $n$ 个人全部出圈，时间复杂度就是 $O(nm)$。
## 代码
```cpp
#include <iostream>
#include <queue> // 使用 queue 需要写头文件
using namespace std;
int main()
{
int n, m;
cin >> n >> m; // 输入
queue <int> q; // 定义队列
for (int i = 1; i <= n; ++i)
{
q.push(i); // 依次插入每一个人的编号
}
int num = 0;
while (!q.empty()) // 如果队列里还有元素就一直循环
{
num += 1; // 当前的人报的数
int a = q.front(); // 存储队首元素
q.pop(); // 弹出队首元素
if (num == m) // 如果报到 m
{
num = 0; // 重新开始报数
cout << a << " "; // 输出编号
continue; // 重新开始循环
}
q.push(a); // 否则再次插入编号
}
return 0; // 完结撒花！
}
```
:::success[你可以]
点个赞再走吧！
:::
:::warning[注意]
不要复制题解，会棕名的！
:::