HDU2925 Musical Chairs(约瑟夫环)

March 13, 2016

题目链接

约瑟夫环: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;
}

Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]