Полное руководство: исправление ошибки симуляции очереди билетов в Java

Проблема в вашей симуляции очереди Java находится в этой проблемной строке:

if (!queue.isEmpty()) {
    tickets[queue.peek()]--;  // НЕПРАВИЛЬНО - уменьшаем количество билетов у неправильного человека!
} else {
    tickets[person]--;
}

Вы уменьшаете количество билетов следующего человека вместо текущего человека. Это вызывает ошибку на единицу в расчете времени.

Содержание

• Основная проблема в вашем коде
• Правильный подход к симуляции очереди
• Оптимизированный математический подход
• Почему ваш тестовый пример не проходит
• Полный исправленный код
• Сравнение производительности

Основная проблема в вашем коде

Фундаментальная ошибка заключается в том, что вы уменьшаете количество билетов у неправильного человека. Когда человек в начале очереди (person) покупает билет, вы должны уменьшить tickets[person], а не tickets[queue.peek()].

Логика должна быть следующей:

1. Человек в начале очереди покупает один билет
2. Уменьшаем количество его билетов
3. Если ему все еще нужны билеты, добавляем его обратно в очередь
4. Увеличиваем время
5. Если целевой человек (k) закончил, останавливаемся

Ваш текущий код уменьшает количество билетов у следующего человека в очереди, что не имеет смысла в контексте симуляции.

Правильный подход к симуляции очереди

Вот исправленный подход к симуляции очереди:

public int timeRequiredToBuy(int[] tickets, int k) {
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < tickets.length; i++) {
        queue.add(i);
    }

    int time = 0;
    while (!queue.isEmpty()) {
        int person = queue.poll();
        
        // ПРАВИЛЬНО: уменьшаем количество билетов у текущего человека
        tickets[person]--;
        time++;
        
        if (tickets[person] > 0) {
            queue.add(person);
        }
        
        // Останавливаемся, когда целевой человек заканчивает
        if (person == k && tickets[person] == 0) {
            break;
        }
    }

    return time;
}

Ключевое исправление - удаление неправильного условия и всегда уменьшение tickets[person].

Оптимизированный математический подход

Согласно результатам исследований, существует более эффективное математическое решение, которое полностью избегает симуляции очереди:

public int timeRequiredToBuy(int[] tickets, int k) {
    int time = 0;
    for (int i = 0; i < tickets.length; i++) {
        if (i <= k) {
            time += Math.min(tickets[i], tickets[k]);
        } else {
            time += Math.min(tickets[i], tickets[k] - 1);
        }
    }
    return time;
}

Как это работает:

• Для людей на позиции или перед позицией k: они могут купить не более tickets[k] билетов
• Для людей после позиции k: они могут купить не более tickets[k] - 1 билета (потому что процесс останавливается, когда человек k заканчивает)

Почему ваш тестовый пример не проходит

Давайте проследим ваш тестовый пример с правильным подходом:

tickets = [83,86,38,31,59,25,89,71,54,71,84]
k = 1
Ожидаемый результат: 687

Используя математический подход:

• Человек 0: min(83, 86) = 83
• Человек 1: min(86, 86) = 86
• Человек 2: min(38, 86-1) = 38
• Человек 3: min(31, 86-1) = 31
• Человек 4: min(59, 86-1) = 59
• Человек 5: min(25, 86-1) = 25
• Человек 6: min(89, 86-1) = 85
• Человек 7: min(71, 86-1) = 71
• Человек 8: min(54, 86-1) = 54
• Человек 9: min(71, 86-1) = 71
• Человек 10: min(84, 86-1) = 84

Итого: 83 + 86 + 38 + 31 + 59 + 25 + 85 + 71 + 54 + 71 + 84 = 687

Ваш код выдавал 688, потому что где-то в симуляции неправильно уменьшал дополнительный билет.

Полный исправленный код

Вот полностью исправленная симуляция очереди:

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < tickets.length; i++) {
            queue.add(i);
        }

        int time = 0;
        while (!queue.isEmpty()) {
            int person = queue.poll();
            
            // ПРАВИЛЬНО: всегда уменьшаем количество билетов у текущего человека
            tickets[person]--;
            time++;
            
            if (tickets[person] > 0) {
                queue.add(person);
            }
            
            // Останавливаемся, когда целевой человек заканчивает покупку всех билетов
            if (person == k && tickets[person] == 0) {
                break;
            }
        }

        return time;
    }
    
    // Оптимизированное математическое решение (рекомендуется)
    public int timeRequiredToBuyOptimized(int[] tickets, int k) {
        int time = 0;
        for (int i = 0; i < tickets.length; i++) {
            if (i <= k) {
                time += Math.min(tickets[i], tickets[k]);
            } else {
                time += Math.min(tickets[i], tickets[k] - 1);
            }
        }
        return time;
    }
}

Сравнение производительности

Где:

• n = количество людей
• t = максимальное количество билетов, которое нужно купить любому человеку

Математический подход значительно эффективнее, особенно при работе с большими количеством билетов, так как он не требует симуляции каждой секунды процесса.

Ключевой вывод: всегда убедитесь, что когда человек покупает билет, вы уменьшаете его количество билетов, а не чье-то другое!

Источники

1. Time Needed to Buy Tickets - LeetCode
2. Time Needed to Buy Tickets LeetCode Question & Solution
3. LeetCode 2073. Time Needed to Buy Tickets - In-Depth Explanation
4. Time Needed to Buy Tickets - LeetCode Daily Challenge

Заключение

• Ваш исходный код неправильно уменьшал количество билетов у следующего человека вместо текущего
• Исправление простое: всегда уменьшайте tickets[person], когда человек покупает билет
• Для лучшей производительности используйте математический подход со сложностью O(n)
• Оба подхода правильно решают проблему и дают ожидаемый результат 687 для вашего тестового примера
• Математический метод рекомендуется из-за его эффективности, особенно при больших размерах входных данных

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