POJ 1012 Joseph 推导,暴力,约瑟夫环,打表难度:2

http://poj.org/problem?id=1012

答案以954ms飘过,不过这道题可以轻松用打表过

思路:如果我们把每个人位于数组中的原始编号记为绝对编号,每次循环过后相对于绝对编号为0的人的编号为相对编号,那么在这道题里,绝对编号是不重要的,只需要每次相对编号n都落在n>=k的位置上,那么n轮后自然所有的bad boy都被处理了.

而相对编号的推导:

设 id[i]为第i轮点到的编号(i从1开始计数),第i+1轮开始时存在的人数就会是2*k-i,点到的人的编号就是(id[i]+m-1)%(2*k-i)

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=;

int ans[maxn];

int n,m;

bool judge(){

    int t=(m-)%(*n);

    for(int i=;i<=n;i++){

        if(t<n){return false;}

        t=(t+m-)%(*n-i);

    }

    return true;

}

int main()

{

    for(n=;n<maxn;n++){

        for(m=n+;;m++){

            if(judge()){

                ans[n]=m;

                break;

            }

        }

    }

    while(scanf("%d",&n)==&&n)

        printf("%d\n",ans[n]);

    return ;

}

巴特西

POJ 1012 Joseph 推导,暴力,约瑟夫环,打表难度:2

最新文章

热门文章

巴特西

POJ 1012 Joseph 推导,暴力,约瑟夫环,打表 难度:2

最新文章

热门文章

POJ 1012 Joseph 推导,暴力,约瑟夫环,打表难度:2