Blog·Tanky WooABOUTRSS

Grid POJ 2746 约瑟夫问题

09 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

比较经典的模拟题,注意对细节的考虑,以及对过程的模拟。

内存: 1848kB 时间: 16ms 语言: C++

// Grid 2746 Joseph
// Author: Tanky Woo
#include
#define MAX 301
int aLoop[MAX];

// www.wutianqi.com
int main()
{
    int n, m;
    int i;
    while(scanf("%d %d", &n, &m) && n && m)
    {
        for(i = 0; i < n; i++)
            aLoop[i] = i+1;
        int nPtr = 0;
        for(i = 0; i < n; i++)
        {
            int nCnt = 0;
            while(nCnt < m)
            {
                while(aLoop[nPtr] == 0)
                    nPtr = (nPtr+1)%n;
                nCnt++;
                nPtr = (nPtr+1)%n;
            }
            nPtr--;
            if(nPtr < 0)
                nPtr = n-1;
            if(i == n-1)
                printf("%d\n", aLoop[nPtr]);
            aLoop[nPtr] = 0;
        }
    }
    return 0;
}