P1996 约瑟夫问题

添加链接描述

这道题是一道很经典的队列例题。有很多种方法可以解决：

比如：模拟链表

先说明一下什么是模拟链表，
模拟链表就是利用数组来实现链表干的事情
实际上模拟这种方法的关键在于“找规律”，找到链表的本质，再通过这个本质模拟出以这个本质为基础的另一种表达。这个“本质”就像数学公式一样，变化无穷。

数组net[i]表示编号为i的学生后面的学生编号是net[i]。
这样形成一个链表：

#include
using namespace std;
int net[1000005];  //数组存放的是学生编号
int main() 
{
	int n, m;
	cin >> n >> m;//输入n、m
	for (int i = 0; i < n; i++)//初始化
		net[i] = i + 1;
	net[n] = 1;
	int p = 0;
	for (int i = 1; i <= n; i++) 
	{//开始模拟出圈过程
		for (int j = 1; j < m; j++)
			p = net[p];//p位置右移
		cout << net[p] << " ";//输出出圈人的位置
		net[p] = net[net[p]];//删掉出圈人,实际上就是将当前的人连接后面一第二个，
	}
	return 0;
}