约瑟夫环问题:获取在剩余t个人时,最后一个被挑出来的人

/*
O(n)获取任意步骤的结果
每一轮报数,报到m的人就被杀掉
例如:n=5,s=1,m=3
第一轮:1 2 3 4 5,排除3,剩下1 2 4 5
第二轮:4 5 1 2,排除1,剩下4 5 2
第三轮:2 4 5,排除5,剩下2 4
第四轮:2 4,排除2,剩下4
最后剩下4
对于第二轮的4 5 1 2,修改编号为1 2 3 4,这样可以发现:
设修改编号之后的每个元素编号为x,每个x修改之前对应的元素编号为y,
则有y==(x+m)%(t) (注意边界)(t是未排除之前的元素个数)
而同时,可以发现:如果把每一步去掉的元素的编号x设为0,y符合上述表达式
所以可以使用递推式:
设f[i]为i个人玩最后的胜利者,定义f[0]=0,有下列表达式成立:
f[1]=(f[0]+m)%1
f[2]=(f[1]+m)%2
f[3]=(f[2]+m)%3
以此类推。(不考虑边界)
那么f[n]就是最后的胜利者。

同时,如果设在被去掉的元素之后,剩余t个元素时,这个被去掉元素编号为g:
那么g可以写成一个递归/递推函数
当这个元素被去掉时,它的编号一定是0,此时f[0]=0,这里f是这个元素在前若干步中的编号
f[1]=(f[0]+m)%(t+1)
f[2]=(f[1]+m)%(t+2)
f[3]=(f[2]+m)%(t+3)
以此类推。(不考虑边界)
那么g=f[n-t]
*/
int Josephus2(int* f,int n,int s,int m,int t){//t为剩余人数
    f[0]=0;
    for(int i=1;i<=n;i++){
        f[i]=(f[i-1]+m)%(t+i);
        if(f[i]==0)f[i]=t+i;
    }
    int g=f[n-t];
    return g+s-1<=n?g+s-1:g+s-1-n;
}

  

上一篇:BZOJ2428 HAOI2006均分数据(模拟退火)


下一篇:公司的雪花算法