King's Game---hdu5643（约瑟夫环）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5643

 

 约瑟夫环问题的原来描述为，设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到k时停止报数，报k的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报k的出圈，……，如此

下去，直到所有人全部出圈为止。当任意给定n和k后，设计算法求n个人出圈的次序。  稍微简化一下。  问题描述：n个人（编号0~(n-1))，从0开始报数，报到(k-1)的退出，剩下的人继续从0开始报数。求胜利者的编

号。 

第一次报数时出局的编号为 k - 1；接下来从 编号为 k 的开始， 依次变为编号为 0,1,2,3,4.....n-1 ；那么以此类推当本次编号为 x 在上一局中的编号为 （x+k）% i ；i 是上一局有多少人；

我们假设获胜的人的编号z（在第一局还没开始的时候的编号）；因此我们用 f[i]表示在倒数第i局中 z 这个人所在编号为 f[i]； 所以f[1] = 0;

int f[N] ={ 0 };

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

{

        f[i] = (f[i-1] + k) % i;

}

　　本题中稍微做了一点改变就是k是变化的，不是固定的

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <stdlib.h>

#include <queue>

#include <map>

using namespace std;

typedef long long LL;

#define met(a, b) memset(a, b, sizeof(a))

#define INF 0x3f3f3f3f

#define N 5210

int main()

{

    int T, n, f[N] = { 0 };

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        int k = n-1;

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

        {

            f[i] = (f[i-1] + k) % i;

            k --;

        }

        printf("%d\n", f[n] + 1);

    }

    return 0;

}