约瑟夫问题|的思路链接

约瑟夫问题|链接

顺着约瑟夫问题|的思路：

  • 循环的条件改变：不再是无脑取m个丢1个；每轮的筛选规则不一样，所以引入sum控制本轮循环次数，j表示报数的周期
  • 第一轮筛选和后面的不同（被坑了）：好好理解“接着第二轮再从上一轮最后一个报数的人开始”，第二轮开始，队列中的最后一个元素放到最前面，报数为1，一定不会被丢掉，所以本轮循环次数不再是队列长度，而是队列长度-1；而本来队列中的其他人报数变为其次序+1（队头元素从2开始报数）
class Joseph {
public:
    int getResult(int n) {
        queue<int>s;
        for(int i=1;i<=n;i++){//初始入队
            s.push(i);
        }
        int j=2;//报数周期
        int sum;
            while(s.size()>1){
                sum=s.size();//每轮报数次数，用于控制循环
                 int k;//区分第一轮和其他轮
                if(j==2)k=0;
                       else k=1;//其他轮：循环次数-1，报数=次序+1
                for(int i=1;i<=sum-k;i++){//(1)
                   if((i+k)%j==1){//(2)
                       s.push(s.front());
                       s.pop();
                   }
                    else {
                        s.pop();
                        if(s.size()==1){return s.front();}
                    }
                }
                j++;
            }
        return 1;//输入只有1人，返回1
        
    }
};