题解 P1996 【约瑟夫问题】

· · 题解

这题我原来打的暴力，但当我学了数据结构后，发现队列居然跑得如此轻松！

约瑟夫问题最难的就是人数在不断变化，数组模拟是很麻烦的，但是线性数据结构的数据数也是不定的，这个问题自然也就迎刃而解了。而这道题，我选择了队列这种先进先出的数据结构。（其实是因为我链表没学好）

我们从1开始数到m，其实就相当于将队列的头部放到尾部m-1次。记住，是m-1次，我原来弄成了m次，在样例上调了好久。

接下来就是你们最喜欢的代码了（15ms，788KB）：

#include<bits/stdc++.h>//漂亮的万能头 
using namespace std;
int n,m;
queue<int>q;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        q.push(i);
    }
    while(!q.empty()){
        for(int i=1;i<m;i++){//注意：是m-1次 
            q.push(q.front());//将头部放至尾部 
            q.pop();
        }
        cout<<q.front()<<" ";//出列+输出 
        q.pop();
    }
    return 0;
}
/*STL的数据结构真好用*/

希望看到此题解的童鞋们NOIp2019rp++！！！