POJ 1012

深碍√TFBOYSˉ_ 2024-04-17 05:25 76阅读 0赞

大致题意：

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

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

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

由于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轮剩余的人数)**

\***举个例子：k=3,n=6,m=5时：  
原始排列：1 、2 、3 、4 、5 、6  
第一个kill:ans\[1\]=(0+5-1)%6=4;（杀死编号4+1=5，即编号5的人）  
新的序列：1 、 2 、 3 、4 、6 （6补位到5的空位上，变成5）  
即：1 、2 、3 、4 、5  
第二个kill:ans\[2\]=(4+5-1)%5=3;(杀死编号3+1=4，即编号4的人)  
新的序列：1、2 、3 、 5（5补位到4的空位上，变成4）  
即：1 、2 、3 、4  
第三个kill:ans\[3\]=(3+5-1)%4=3;(杀死编号为3+1=4，即编号4的人)  
剩余序列：1、 2、 3  
坏人全部清除。如果ans\[i\]<k说明杀死了好人，跳出，枚举下一个m**

特别需要注意的是k<14,因为k值较少，那么POJ的数据测试就极有可能重复测试每个k值的结果，那么为了减少总体的时间，我们可以通过服务器打表，我们的程序只在第一次得到k值的时候计算出了m值，然后保存下来，当k值再次出现时，就直接把保存的结果输出，不用再重复计算m。

上代码：

#include <iostream>
    using namespace std;
     
    int main()
    {
     int joseph[14]={0};
     int k;
     while(cin>>k&&k!=0) 
     {
     	if(joseph[k])
     	{
     		cout<<joseph[k]<<endl;
     		continue;
    	 }
    	 int ans[30]={0};
    	 int n=2*k;
    	 int m=k+1;
    	 for(;;m++)
    	 {
    	 	int flag=1;
    	 	for(int i=1;i<=k;i++)
    		 {
    	 		ans[i]=((ans[i-1]+m-1)%(n-i+1));
    	 		if(ans[i]<k)
    	 		{
    	 		flag=0;
    	 		break;
    		 }
    	 }
    	 if(flag) break;
    	 }
    	 joseph[k]=m;
    	 cout<<m<<endl;
     }
    }