题目地址:http://poj.org/problem?id=1012
问题描述:约瑟夫问题是这样一个问题,N个人围成一个圆圈,分别给每个人编号1,2,3,……,N。第一轮从1号人物开始报数,报到第M个人时,第M个人自杀,并退出圆圈;接着从自杀的这个人往后一个人开始从1继续报数,报到M时,第M个人自杀;重复这一过程,直到只有最后一个人存活下来。
POJ1012中的这道题目对约瑟夫问题做了一些改动:
(1)限制了圈内的人数为2K,0<K<14
(2)认为前k个人为好人,后k个人为坏人,要求求得的M在杀死所有坏人前不准杀死一个好人。
基于以上理解,得到如下解题思路:
首先,针对第一轮,因为前k个人是好人,不能自杀,那么要求的M的值一定大于等于k;并且只需判断前k个自杀的人是不是都在后k个位置
其次,针对每一轮,假设当前自杀的人为die,当前轮的总人数为currLen,那么下一轮自杀的人肯定是(die+M-1)%currLen;
在对当前M进行判断时,只有当已经自杀的k个人不在前k个位置时,才是所求的M;否则,M加一,继续求解。
在我的VS下,测试两组数据,均得到正确结果。
提交代码时,却提示“Time Limit Exceeded”。仔细一看题目,原来有时间限制——Time Limit:1000MS
为了解决这个问题,不防先把计算出的k=1,2,3,……,13时的M值保存到数组中。
修改之后的代码为: