Preface

学校码图的数据结构实验第一题，因为是码图~~所以可以随便欺负~~,所以不需要写很高效的算法应该也能过吧；

但是鉴于码图的落后性，一些高级的新特性可能会编译不通过（据说内部编译器是VC2014），最多支持到c99；

让我们开始吧！

Content

这里是题目:Josephus环

用循环链表实现：N个乘客同乘一艘船，因为严重超载，加上风高浪大，危险万分，因此船长告诉乘客，只有将部分乘客投入海中，其余人才能幸免于难。无奈，大家只得同意这种办法。于是N个人围成一圈(从1，2，3...N分别编号)。由编号为1的人开始，依次报数，数到第M人，便把他投入大海中，然后再从他的下一个人数起，数到第M人，再将他扔到大海中，如此循环地进行，直到剩下K个乘客为止。按顺序依次输出被扔下大海的乘客的编号。

提交格式：实现int * solve(int N,int M,int K)函数。函数参数为乘客人数N、间隔人数M和剩余乘客人数K，1<=N<=1000，1<=M<=500000，0<=K<N。函数返回值为按顺序被扔下大海乘客编号的数组。请不要printf输出任何内容。

输入样例1： 9 3 2 输出样例1： 3 6 9 4 8 5 2

输入样例2： 12 5 6 输出样例2： 5 10 3 9 4 12

~~你让我用循环链表我就用?~~ 比较简单的办法当然是用数组来模拟链表，并且一个简单的优化就是报完数后应该等效为最多转一圈；

直接贴代码

int *solve(int N, int M, int K){
    const int maxn=1005; 
    int nxt[maxn];
    int pre[maxn];

    int *a=new int[N-K];
    int in=1; 
    for(int i=1;i<=N;i++) nxt[i]=i%N+1;
    for(int i=1;i<=N;i++) pre[i]=(i-1)%N+(i==1)*N;    

    for(int now=N;now>K;now--){
        int m=(M+now-1)%now+1;
        for(int cnt=1;cnt<m;in=nxt[in],cnt++); 
        a[N-now]=in;
        nxt[pre[in]]=nxt[in];
        pre[nxt[in]]=pre[in];
        in=nxt[in]; 
    }
    return a;
}