有些人站在队列中。选择过程遵循一个规则，即选择站在偶数位置的人。在选定的人员中，形成一个队列，再次从这些人员中仅选择偶数位置的人。这种情况一直持续到我们只剩下一个人。找出该人在原始队列中的位置。
我如何修改代码，以便在队列中有奇数个元素时它起作用，因为在某些时候(在 while 循环中)，队列肯定会有奇数个元素。
int main()
{
int temp=0,x,n,i;
cin>>x;
while(x--) {
cin>>n;
queue<int> q;
for(i=1;i<=n;i++)
q.push(i);
while(q.size()!=1) {
q.pop();
temp=q.front();
q.pop();
q.push(temp);
}
cout<<temp;
}
return 0;
}
输入：5 预期输出：4
关键在于问题陈述：在选定的人员中形成一个队列。 当您从q中选择人员时，不要将他们放回同一队列中，而是将他们放入新队列中。 完成该选择后，swap两个队列(以将旧队列替换为新队列)，然后再继续下一个迭代。
基本问题似乎是您将所选位置放在队列的末尾，将新队列附加到旧队列中。如果新队列的开始对应于while循环迭代的开始，这将起作用。但是，当旧队列的长度为奇数时，这不起作用。
您的方法的下一步是，如果长度为奇数，则从旧队列中删除最后一个元素。这为您提供了一个有效的偶数长度队列。新问题是弄清楚何时找到新队列的开头，以便您可以重复该过程(检查奇数长度)。
执行此操作的一种方法是在队列的开头放置一个哨兵值。因此，在构建初始队列时，请使用0到n的数字构建它，而不仅仅是1到n。循环要做的第一件事是检查队列的前端是否为零。如果是，请弹出它，强制剩余队列具有均匀长度，然后在末尾按零。之后，按照您的要求继续(啪，啪，推)。
一种不太神秘的方法是使用两个队列而不是模拟两个队列。
更快的方法是删除循环并使用公式。(哪个公式？这是一个合理的数学练习，所以我会把它留给你来弄清楚。特别是因为原始问题也是一种练习。我只想提一下，数学涉及 2 的幂。