[AcWing3253. 游戏]

有 n 个小朋友围成一圈玩游戏，小朋友从 1 至 n 编号，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 号小朋友获胜。

给定 n 和 k，请问最后获胜的小朋友编号为多少？

输入格式

输入一行，包括两个整数 n 和 k，意义如题目所述。

输出格式

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

数据范围

对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ 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
38
#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，剩下一个
    // 已知 hh <= tt，循环条件为：队列不为空则一直...
    // 那么: hh < tt，循环条件为：队列不为1个则一直...
    while(hh < tt){
        // 如果当前编号的小朋友不该枪毙
        if(j % k && j % 10 != k){
            // 重新排队
            q[++tt] = q[hh];
            ++hh;
        }else{
            ++hh; // 该枪毙就枪毙
        }
        j++;
    }
    // 输出剩下的唯一一个在队首的小朋友
    cout << q[hh] << endl;
    
    return 0;
}