HDU2925 Musical Chairs(约瑟夫环)

题目链接

约瑟夫环:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。

为取模方便,假设下标从0开始,倒推分析:

假设该轮有n个人,那么上一轮(n+1)人,编号为0的人上一轮编号为k,也即编号为f[n]的人上一轮编号为(f[n]+k)%(n+1)。

我们知道最后剩下的人在最后一轮编号肯定为0,那么这样不断倒推就可以推出其在第一轮的编号,也即他本来的编号。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int f[1000005];
int main(){
    //freopen("a.txt", "r", stdin);
    int n, m;
    while(~scanf("%d%d", &n, &m) && n && m){
        f[1] = 0;
        for(int i = 2; i <=n; i++){
            f[i] = (f[i-1]+m)%i;
        }
        cout << n << " " << m << " " << f[n]+1 << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 约瑟夫环