这道题,似乎是半“隐私”题,我先看看吧。给个题目简介。
【题目描述】
由经典约瑟夫问题改成。
有NN个猴子,编号从11到NN。每个猴子对应一个正整数XiXi,表示如果从编号为ii的猴子开始报数,需要数到XiXi。
这NN个猴子围成一圈,从第一个开始报数,数到第11个猴子对应的正整数X1X1的猴子出队,然后从它的下一位继续从11开始报数,数到对应的XiXi时出队,如此循环直到剩下一个猴子,最后剩下的那个猴子就是猴子们选出的大王。
例如:
N=5,XiN=5,Xi对应为:1,2,3,4,51,2,3,4,5。
出队的顺序为:1,3,4,51,3,4,5。
【输入】
第一行为NN;
第二行为NN个小于等于100100的正整数。对应于从某个猴子位置开始报数,需要报数的次数。
【输出】
被选为大王的猴子的编号。
【输入样例】
5
1 2 3 4 5
【输出样例】
2
好勒,这道题思路其实是模拟,直接上代码。
#include <bits/stdc++.h>
using namespace std;
int n,a[1000050],tot,m;
int main()
{
cin>>n;
queue<int>q;//队列
for(int i=1; i<=n; ++i)
{
scanf("%d",&a[i]);
q.push(i);//输入并入队
}
m=a[1];//第一个要求的数其实就是a[1]
while(q.size()!=1)//还没出“大王”
{
++tot;//继续报数
int v=q.front();
q.pop();
if(tot!=m) q.push(v);//如果没到要求的m,就把这人入队,继续报
//这有点似循环队列。
else
{
tot=0;
m=a[q.front()];//不然让他出队,并更换要求的数m
}
}
cout<<q.front()<<endl;//输出“猴王”
return 0;
}
这次代码,其实挺简单的,我就不写太多了,再见。