题目描述

有 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

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 1010;

int n,k;
bool st[N];

// 判断当前的报数是否合法
bool check(int x){
    if(x % k == 0 || x % 10 == k)   return false;
    return true;
}

int main()
{
    cin>>n>>k;
    int cnt = 0;//玩家报数
    int now_id = 1;//玩家编号
    int res = n;//res减到1即结束游戏，res人数
    memset(st,1,sizeof st);//刚开始都没有淘汰
    while(res!=1)
    {
        if(now_id > n) now_id = 1;
        if(st[now_id])
        {
            cnt++;
            if(check(cnt) == 0)//报数不合法
            {
                st[now_id] = false;//淘汰
                res--;//玩家数量减一
            }
        }
        now_id++;
    }
    for(int i = 1; i<=n; i++)
    {
        if(st[i]) 
        {
            cout<<i;
            return 0;
        }
    }
    return 0;
}

法2：队列

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 1010;

int n,k;
bool st[N];

int main()
{
    cin>>n>>k;
    queue<int> q;
    for(int i = 1; i<=n; i++) q.push(i);
    int j = 1;
    while(q.size()>1)
    {
        int x = q.front();
        q.pop();
        if(j%k && j%10!=k) q.push(x);
        j++;
    }
    cout<<q.front();
    return 0;
}