原题链接: AcWing

题目描述:

某公司招聘，有 n 个人入围，HR在黑板上依次写下 m 个正整数 A1,A2,…Am，然后这 n 个人围成一个圈，并按照顺时针顺序为他们编号 0,1,2,…n−1。 录取规则是： 第一轮从 0 号的人开始，取用黑板上的第 1 个数字，也就是 A1。 黑板上的数字按次序循环使用，即如果某轮用了第 k 个，如果 k < m，则下一轮需要用第 k+1 个；如果 k=m，则下一轮用第 1 个。 每一轮按照黑板上的次序取用到一个数字 Ax，淘汰掉从当前轮到的人开始按照顺时针顺序数到的第 Ax 个人。 下一轮开始时轮到的人即为被淘汰掉的人的顺时针顺序下一个人，被淘汰的人直接回家，所以不会被后续轮次计数时数到。 经过 n−1 轮后，剩下的最后 1 人被录取，所以最后被录取的人的编号与 (n,m,A1,A2,…Am) 相关。

输入格式

输入包含多组测试数据。 第一行包含整数 T，表示共有 T 组测试数据。 接下来 T 行，每行包含若干个整数，依次存放 n,m,A1,A2,…Am，表示一组数据。

输出格式

输出共 T 行，每行对应相应的那组数据确定的录取之人的编号。

数据范围

0 < T < 10, 0 < m, Ax < 10^3, 0 < n < 10^7

输入样例：

1
4 2 3 1

输出样例：

1

样例解释

样例里只有 1 组测试数据，说的是有 4 人入围（编号 0∼3）。 黑板上依次写下 2 个数字：3、1，那么： 第一轮：当前轮到 0 号，数到数字 3，顺时针数第 3 个人是 2 号，所以淘汰 2 号，下一轮从 3 号开始，目前剩余：0、1、3； 第二轮：当前数到 3 号，取到数字 1，顺时针数第 1 个人是 3 号，所以淘汰 3 号，下一轮从 0 号开始，目前剩余：0、1； 第三轮：当前轮到 0 号，循环取到数字 3，顺时针数第 3 个人是 0 号，所以淘汰 0 号，最后只剩下 1 号，所以录取 1 号，输出 1；

解题思路:

这道题是一个典型的约瑟夫环问题，不同的就是把报数从3变成了另一个循环的数组，虽然可以依靠循环链表直接模拟出来，但是由于数据范围过大，用链表模拟会超时，因为链表的 new 操作是非常慢的，所以只能依靠数组， 但是我在尝试了用数组模拟循环链表后依旧超时，这时就只有依靠数学方法了，看来数学是一个永远绕不过去的坑，只有接受它才能让我继续前进。

循环链表模拟代码:（超时，通过6/10个数据）

#include <iostream>
using namespace std;
const int N=1e3+1;
int answer[N];
typedef struct node
{
    int data;
    struct node *next;
}*PQ,st;
int main()
{
    int n,m,t,i,pos = 0,count = 0;
    cin>>t;
    PQ head,tail,p,q;
    head = new st;
    head->data = -1;
    head->next = nullptr;
    while(t--)
    {
        cin>>n>>m;
        tail = head;
        for(i = 0;i<n;++i)
        {
            p = new st;
            p->data = i;
            tail->next = p;
            p->next = head->next;
            tail = p;
        }
        for(i = 0;i<m;++i)
        {
            cin>>answer[i];
        }
        p = head->next;
        q = tail;
        i = 1;
        count = answer[pos];
        while(p!=q)
        {
            if(i==count)
            {
                q->next = p->next;
                delete p;
                p = q->next;
                i = 1;
                pos = (pos+1)%m;
                count = answer[pos];
            }
            else
            {
                q = p;
                p = p->next;
                i++;
            }
        }
        cout<<p->data<<endl;
        delete p;
        head->next = nullptr;
        pos = 0;
        count = 0;
    }
    delete head;
    return  0;
}

数学方法是几种约瑟夫环解法里面最简短的，同时也是最难理解的，我本人也是理解不了，不过也许若干年后再回来看时就能够理解了

数学方法实现代码：

#include <iostream>
using namespace std;

const int N = 1e3 + 10;
int a[N];

/*
约瑟夫环递推公式：
    f(1) = 0;     //表示最后一轮的胜出者当前编号是0
    f(x) = (f(x - 1) + m) % x , 1 < x <= n //每一轮都找到胜出者在上一轮中的编号
    不过本题里m是在变化的，所以要相应地变为：
==> f(x) = (f(x - 1) + a[(n - x) % m]) % x, 1 < x <= n
*/

int main()
{
    int T;
    cin >> T;
    while(T --){
        int n, m;
        cin >> n >> m;
        for(int i = 0; i < m; ++ i) scanf("%d", &a[i]);

        int ret = 0;
        for(int i = 2; i <= n; ++ i){
            ret = (ret + a[(n - i) % m]) % i;
        }
        cout << ret << endl;
    }
    return 0;
}