看到这个题,首先想到了约瑟夫环,这不就是一个变种的约瑟夫环吗,但n的最大值为10910^9109,显然使用数组和队列解决约瑟夫环的方法,因为超存储和超时在这里无法使用。又想到曾做过一道约瑟夫环问题:A101157.约瑟夫问题,使用跳变的方式加速找到元素,貌似可以规避掉超存储和超时间的问题,但这个方法最后只做到了得到剩余的元素数量,而无法获知剩余元素的原始编号,而如果要对应起来,显然又涉及到存储问题。
这里开始思考:如何可以从最后的剩余元素个数推出这些元素的原始编号。重复操作的停止条件是剩余凋零骷髅的个数不足4只;而从这不足4只再回推原始编号。哈,灵光乍现——递进+回归——递归。
傻子一个,本来就是在做递归专题的题目呀,不是递归是什么。
递进过程很好想到:只要大于等于4个,就重复操作:四个组队走,剩一个;不够组队都剩下
回归过程:回归要从返回的结果推出现在的编号,而推现在的编号需要知道有几个完整的队以及非完整队的元素个数。
具体代码实现如下,代码中也有注释,应该还是比较好理解的。