这道题其实和约瑟夫问题差不多嘛~
用队列模拟一下这个过程就可以过啦!~~知道思路想要AC Code的直接下拉qwq~~
不知道队列是什么的同学可以baidu一下,或者看看这个:
https://oi-wiki.org/ds/queue/
具体思路:
首先准备两个容器:
queue<int>q;stack<int>s;
queue是用来模拟队列的。
而stack则用于存放出队的成员,我们需要求的最后一个出队成员正好就在栈顶。
因为这题数据很松,所以直接开始枚举m
然后,将队列的成员入队
下面是关键语句:
while(!q.empty())//队列非空时候进行模拟
{if(cnt%m==0){s.push(q.front());//把出队的成员入栈 q.pop();cnt++;} //模拟出队else{q.push(q.front());q.pop();cnt++;}//如果暂时不需要出队就塞入队尾
}
想象一下这个过程是怎么样的吧,从1开始走,我们先让1出队,并且压入栈中,然后通过cnt计算走了多少步
当cnt%m=0的时候,就意味着相应的元素需要入栈、出队;
如果cnt%m≠0,我们认定这个成员暂时不需要出队,把他压入队尾即可。
~~理解了这些,就可以AC啦~~AC Code:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef unsigned long long ll;
int main(){int n;while(cin>>n&&n!=0){queue<int>q;stack<int>s;for(int m=1;m<=n;m++)//开始枚举m {for(int i=1;i<=n;i++) q.push(i);int cnt=0;while(!q.empty())//队列非空时候进行模拟{if(cnt%m==0){s.push(q.front());//把出队的成员入栈 q.pop();cnt++;} //模拟出队else{q.push(q.front());q.pop();cnt++;}//如果暂时不需要出队就塞入队尾 }if(s.top()==13)//如果最后一个出队的元素确实是13,则输出答案,结束枚举{cout<<m<<endl;break;} } }return 0;
}