当前位置: 代码迷 >> 综合 >> 【题解】UVA151 【Power Crisis】
  详细解决方案

【题解】UVA151 【Power Crisis】

热度:20   发布时间:2024-02-24 14:08:03.0

这道题其实和约瑟夫问题差不多嘛~

用队列模拟一下这个过程就可以过啦!~~知道思路想要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;
}

 

  相关解决方案