[AcWing3253. 游戏]

n 个小朋友围成一圈玩游戏,小朋友从 1n 编号,2 号小朋友坐在 1 号小朋友的顺时针方向,3 号小朋友坐在 2 号小朋友的顺时针方向,……,1 号小朋友坐在 n 号小朋友的顺时针方向。

游戏开始,从 1 号小朋友开始顺时针报数,接下来每个小朋友的报数是上一个小朋友报的数加 1

若一个小朋友报的数为 k 的倍数或其末位数(即数的个位)为 k,则该小朋友被淘汰出局,不再参加以后的报数。

当游戏中只剩下一个小朋友时,该小朋友获胜。

例如,当 n=5, k=2 时:

  • 1 号小朋友报数 1
  • 2 号小朋友报数 2 淘汰;
  • 3 号小朋友报数 3
  • 4 号小朋友报数 4 淘汰;
  • 5 号小朋友报数 5
  • 1 号小朋友报数 6 淘汰;
  • 3 号小朋友报数 7
  • 5 号小朋友报数 8 淘汰;
  • 3 号小朋友获胜。

给定 nk,请问最后获胜的小朋友编号为多少?

输入格式

输入一行,包括两个整数 nk,意义如题目所述。

输出格式

输出一行,包含一个整数,表示获胜的小朋友编号。

数据范围

对于所有评测用例,1 ≤ n ≤ 10001 ≤ k ≤ 9

输入样例1:

1
5 2

输出样例1:

1
3

输入样例2:

1
7 3

输出样例2:

1
4

算法思想

这是经典的约瑟夫问题。采用数组模拟,但要注意:没有环,但是怎么实现环的效果呢?
采用重新入队的方式

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

using namespace std;

const int N = 1000010;

int q[N], hh = 0, tt = -1;

int main(){

int n, k;

// n个小朋友,幸运数字k
cin >> n >> k;
// 小朋友排队等待枪毙
for(int i = 1; i <= n; i++) q[++tt] = i;

// 编号
int j = 1;
// n个小朋友枪毙 n - 1 个,枪毙的号码是幸运数字的k的倍数或末尾数为k,剩下一个
// 以小朋友剩下个数为循环跳出条件 tt - hh = 0的情况代表队列还有一个小朋友
while(tt - hh > 0){
// 如果当前编号的小朋友不该枪毙
if(j % k && j % 10 != k){
// 重新排队
q[++tt] = q[hh];
++hh;
}else{
++hh; // 该枪毙就枪毙
}
j++;
}
// 输出剩下的唯一一个在队首的小朋友
cout << q[hh] << endl;

return 0;
}