加载中...

POJ 1012 - Joseph


问题描述

有 k 个坏人 k 个好人坐成一圈,前 k 个为好人(编号 1~k),后 k 个为坏人(编号 k+1~2k)

现在有一个报数 m,从编号为 1 的人开始报数,报到 m 的人就要自动死去。

问当 m 为什么值时,可以使得在出现好人死亡之前,k 个坏人先全部死掉?

注意 :

  • 当前一轮第 m 个人死去后,下一轮的编号为 1 的人 为 前一轮编号为 m+1 的人
  • 前一轮恰好是最后一个人死掉,则下一轮循环回到开头那个人报 “1”

解题思路

经典的约瑟夫水题。

由于 k 值比较小(1~13),暴力枚举 m 就可以了

递推公式为:

ans[i];  // 第i轮杀掉 对应当前轮的编号为ans[i]的人
ans[0]=0;
ans[i]=(ans[i-1]+m-1)%(n-i+1);  // i>1,  总人数n=2k 则n-i为第i轮剩余的人数

有耐心的同学可以自己推导一下公式,推导时要注意 2 点:

第一点:每轮都是以前一轮死掉的人的后一个人作为 “1” 开始顺序编号的。

如: k=2 (n=4) m=7

1
4
3
2

那么最初的编号如下:

第一轮报数后,3 号被杀掉,那么以 3 号后面的一个人 “4” 作为下一轮的 “1” 重新编号:

第二点f[i]=(f[i-1]+m)%(n-i); (i>1)

这是网上一些地方给出的递推公式,对于本题而言是不正确的。因为这种递推公式针对的是从 0 开始报数的 Joseph,本题是从 1 开始报数的,必须要变形


最后就是由于本题 k 值有限,只有 13 个值,那么 POJ 的数据测试就极有可能重复测试每个 k 值的结果,为了节省总体时间,我们的程序只在第一次得到 k 值的时候计算 m 值,然后保存下来,当 k 值再次出现时,就直接把保存的结果输出,不再计算 m。这是在服务器打表的处理。

另外有了递推的程序后,我们就知道了每个 k 值对应的 m 值。

此时追求 0ms AC 的同学可以利用递推程序的结果,再写一个程序,直接在程序里面打表:

int Joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};

AC 源码

//Memory Time
//184K   250MS 

#include<iostream>
using namespace std;

int main(void)
{
    int Joseph[14]={0};  //打表,保存各个k值对应的m值

    int k;
    while(cin>>k)
    {
        if(!k)
            break;

        if(Joseph[k])
        {
            cout<<Joseph[k]<<endl;
            continue;
        }

        int n=2*k;  //总人数
        int ans[30]={0};  //第i轮杀掉 对应当前轮的编号为ans[i]的人
                          //PS:每一轮都以报数为“1”的人开始重新编号

        int m=1;    //所求的最少的报数
        for(int i=1;i<=k;i++)  //轮数
        {
            ans[i]=(ans[i-1]+m-1)%(n-i+1);   //n-i为剩余的人数
            if(ans[i]<k)  //把好人杀掉了,m值不是所求
            {
                i=0;
                m++;  //枚举m值
            }
        }
        Joseph[k]=m;
        cout<<m<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录