poj1012-Joseph

来源:互联网 时间:1970-01-01

转载请注明出处:優YoU http://user.qzone.qq.com/289065406/blog/1303803255

 

大致题意:

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

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

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

 

PS:当前一轮第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};

 

 

 1 //Memory Time
2 //184K 250MS
3
4 #include<iostream>
5 using namespace std;
6
7 int main(void)
8 {
9 int Joseph[14]={0}; //打表,保存各个k值对应的m值
10
11 int k;
12 while(cin>>k)
13 {
14 if(!k)
15 break;
16
17 if(Joseph[k])
18 {
19 cout<<Joseph[k]<<endl;
20 continue;
21 }
22
23 int n=2*k; //总人数
24 int ans[30]={0}; //第i轮杀掉 对应当前轮的编号为ans[i]的人
25 //PS:每一轮都以报数为“1”的人开始重新编号
26
27 int m=1; //所求的最少的报数
28 for(int i=1;i<=k;i++) //轮数
29 {
30 ans[i]=(ans[i-1]+m-1)%(n-i+1); //n-i为剩余的人数
31 if(ans[i]<k) //把好人杀掉了,m值不是所求
32 {
33 i=0;
34 m++; //枚举m值
35 }
36 }
37 Joseph[k]=m;
38 cout<<m<<endl;
39 }
40 return 0;
41 }

 

 

 

 

我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863 || 我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b || 我的新浪微博:http://weibo.com/lyy289065406 || 我的腾讯微博:http://t.qq.com/lyy289065406 || 我的QQ空间:http://user.qzone.qq.com/289065406 || 我的百度空间:http://hi.baidu.com/you289065406/home || 我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


相关阅读:
Top