POJ 1012-Joseph Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 48397 Accepted: 18267 Description The Joseph’s problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy. Input The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14. Output The output file will consist of separate lines containing m corresponding to k in the input file. Sample Input 3 4 Sample Output 5 30 Source Central Europe 1995
这个题目挺有趣的。有k个好人和k个坏人，依次编号为1~k~2k，其中前k个为好人，后k个为坏人。然后从1开始循环报数，报到m的被杀掉，杀掉之后，从被杀掉的下一个人开始又从1开始循环报数。求最小的m使得在杀好人之前，所有的坏人都已经被杀掉了。 看到这个题很快能得出两个约束条件： 1. 因为坏人的编号大于k，所以m的取值肯定要大于k，要不然第一个杀的肯定是好人。 2. 对于某个m，最多只需要循环杀k个人，我们就能判断这个m是不是所求，杀人的过程中杀到某个人的编号小于等于k，则肯定杀到好人了，但此时还没有杀完所有坏人，所以这个m不是所求，跳出，m++；如果这k个人都成功杀完，则所有坏人都杀完，m是所求。 以上思路都很简单，但是有一个关键问题没有解决：已知第i次杀人的编号是a[i]，那么杀完a[i]后，下一个杀的人的编号是多少呢？如果是环形不杀人，只是报数的话，易知是(a[i]+m-1)%n，但是杀完某个人后下一轮报数时这个人已经不在了，要跳过他，所以编号是(a[i]+m-1)%(n-i)，这就是著名的Joseph环。 有了Joseph环这个结论就很好办了，加上之前的两点结论，我们可以很快的写出代码，如下： [cpp] #include <stdio.h> int main() { int people[28] = {0}, k, Joseph[14] = {0};//k最多是13，people所有人的编号，Joseph用于打表，不然超时 while(scanf("%d", &k) != EOF && k != 0) { if (Joseph[k] != 0)//如果是之前求过的 { printf("%d\n", Joseph[k]);//则直接输出 continue; } int n = 2 * k; int m = k+1;//m从k+1开始测试 people[0] = 0;//people[0] = 0表示编号从0开始 for (int i = 1; i <= k; i++)//最多连续杀k个人 { //每次枚举完毕将剩下的人按从0到n – i编号，只要好人没有杀掉，则前面k – 1个编号是不变的 people[i] = (people[i – 1] + m – 1) % (n – i + 1); if (people[i] < k)//第k个人的编号为k – 1,所以这里是<而不是<= //杀到好人了 { i = 0 ;//重新开始 //有点continue的意思 m++; //测试下一个m } } Joseph[k] = m; printf("%d\n", m); } return 0; } [/cpp] 以上代码参考这个博客，做了微小的调整。代码AC，用时250MS，内存136K。 其实在我不知道Joseph环公式的时候，我用双向链表（其实就是STL里的list）写了一个版本，这个版本很朴实，就是杀一个人之后，把这个节点去掉，然后再循环报数，这样就不需要琢磨下一个被杀的编号到底是多少啊，但是这个版本超时严重。我也把代码贴上来，以供参考。 [cpp] #include<iostream> #include<list> #include<map> using namespace std; //测试m是否是所求 bool check_m(int k,int m) { list<int> li; for(int i=1;i<=2*k;i++) li.push_back(i);//首先初始化链表，人的编号从1开始 int pos=1,executed_num=0;//pos当前报数，executed_num被杀的人数 list<int>::iterator it=li.begin(),tmp; while(executed_num<k)//最多杀k个人就可以判断m { if(pos==m)//如果报数到m了。 { //cout<<*it<<endl; if(*it<=k)//但是编号小于等于k，则杀到好人了。 return false; tmp=it; tmp++; li.erase(it);//否则把这个坏人杀掉并去除这个节点 it=tmp; pos=1;//重新从1开始报数 executed_num++; } else//如果还没报到m，则一直报下去，这个地方可能会消耗比较多的时间 { pos++; it++; } if(it==li.end())//如果到链表尾了，则循环到头 it=li.begin(); } return true; } int main() { int k,m; map<int,int> mii; //用于打表 while(cin>>k&&k) { if(mii.find(k)!=mii.end())//如果之前计算过这个k，则直接输出 { cout<<mii[k]<<endl; continue; } for(m=k+1;;m++) { if(check_m(k,m)) { cout<<m<<endl; mii[k]=m; break; } } } return 0; } [/cpp]]]>