1455.招聘

题目描述
某公司招聘，有 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 行，每行对应相应的那组数据确定的录取之人的编号。
思路
这道题就是典型的约瑟夫环问题。

旧编号用的是f[n,k]即n个人第k个数
新编号用的是f[n-1,k+1]即n-1个人第k+1个数

n个人变n-1个人用的是a[0]
n-1个人变n-2个人用的是a[1]
n-2个人变n-3个人用的是a[2]
...
2个人变1个人用的是a[(n-2)%m]//m为数字的个数，因为m不一定有n长
代码

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
int n,m;
int T;

int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=0;i<m;i++) cin>>a[i];
        int res=0;
        //从n-1开始 用的是a[0] ,n-2 用的 a[1] ... 所以 2用的是a[n-1]
        //所以j从n-2开始往回推 对m取模
        for(int i=2,j=(n-2)%m;i<=n;){
            //f[n,k] 还有n个人，用a[k]去排除人 ， 最后剩下的人的序号是f[n,k]
            //旧编号 ak ak+1 ak+2 ...
            //新编号 0  1    2    ...
            //旧编号就是 新编号 + ak 然后对n取模
            //f[n,k]=(f[n-1,k+1] + a[k])%n
            res=(res+a[j])%i;
            i++;
            if(--j<0) j=m-1;
        }
        cout<<res<<endl;
    }
    return 0;
}