Выбор альтернативных позиций в очереди

Question

Некоторые люди стоят в очереди. Процесс отбора следует правилу, при котором выбираются люди, стоящие на четных позициях. Из отобранных людей формируется очередь, и опять же из этих людей выбираются только люди на четной позиции. Это продолжается, пока мы не останемся с одним человеком. Узнайте положение этого человека в исходной очереди.

Как я могу изменить код так, чтобы он работал, когда в очереди нет нечетных элементов, потому что в какой-то момент (в цикле 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

Answer 1

Ключ в постановке задачи: Из выбранных людей формируется очередь . Когда вы выбираете людей из q, не помещайте их обратно в одну очередь, а помещайте их в новую. Как только вы закончите с этим выбором, swap две очереди (чтобы заменить старую очередь новой очередью), прежде чем переходить к следующей итерации.

Answer 2

Основная проблема заключается в том, что вы помещаете выбранные позиции в конец своей очереди, добавляя новую очередь к старой.Это будет работать, если начало новой очереди соответствует началу итерации вашего цикла while.Однако это не работает, если старая очередь имеет нечетную длину.

Следующим шагом для вашего подхода будет удаление последнего элемента из старой очереди, если длина нечетная.Это дает вам очередь равной длины, которая работает.Новая проблема состоит в том, чтобы выяснить, когда вы нашли начало новой очереди, чтобы вы могли повторить процесс (проверки на нечетную длину).

Один из способов сделать это - поместить значение часовогов начале вашей очереди.Поэтому при построении исходной очереди создайте ее с номерами от 0 до n вместо просто 1 до n.Первое, что должен сделать ваш цикл, это проверить, равен ли фронт очереди нулю.Если это так, вставьте его, заставьте оставшуюся очередь иметь четную длину, а затем нажмите ноль в конце.После этого продолжайте в том же духе (pop, pop, push).

---

Менее загадочный подход состоит в использовании двух очередей вместо симуляции двух очередей.

Более быстрый подходбудет удалить цикл и использовать формулу.(Какая формула? Это разумное математическое упражнение, поэтому я оставлю это вам на усмотрение. Тем более, что исходная задача также является упражнением. Я просто упомяну, что математика включает в себя степени 2.)