猴子选大王-结构体
目录
【问题描述】
有n只猴子围成一圈,从1~n编号,大家决定从中选出一个大王。经过协商,决定选大王的规则为:从编号为1的猴子开始报数,报到k的猴子出圈,然后再从下一只开始继续报1到k,最后剩下来的那一只就是大王。
【输入】
一行,包含两个正整数n和k(2≤n≤1000,2≤k≤109)。
【输出】
一行,一个正整数,表示猴王的编号。
For example:
Input
Result
3 2
3
Answer
#include <iostream>
using namespace std;
struct MONKEY
{
int code;
int next;
};
int main()
{
MONKEY mons[1000];
int n;
int k;
cin >> n >> k;
//init
int i,j,index=1,pre;
for(i=1;i<n;i++)
{
mons[i].code = i;
mons[i].next = i+1;
}
mons[n].code = n;
mons[n].next = 1;
//run
for(i=1;i<n;i++)
{
//do a roll
for(j=1;j<k;j++)
{
pre = index;
index = mons[index].next;
}
//index will leave
mons[pre].next = mons[index].next;
pre = mons[pre].next; //这两句是加的
index = mons[index].next;
}
cout << mons[index].code << endl;
return 0;
}
分析:
这题比较难,老宫上课时写了一段代码,我把它记下来了,提交后发现不能通过全部测试数据。然后我就自己捣鼓。我知道问题是出在//index will leave 这个地方,但我不知道怎么改,最后我就打算放弃了,随便加了两句竟然瞎猫碰死耗子碰对了。
Input
Expected
Got
3 2
3
3
285 844
97
97
Passed all tests!