Задача: "Очередь с поддержкой минимума"

Question

Передо мной стоит задача:

Реализуйте очередь с поддержкой минимума.
Первая строка входных данных содержит число n — количество операций с очередью. В каждой следующей строке содержится число ai (0 ≤ ai ≤ 10000). Если ai > 0, то это число необходимо добавить в очередь. Если ai = 0, то это запрос на удаление элемента из очереди.
На каждый запрос удаления элемента из очереди необходимо вывести значение минимального элемента очереди (учитывая значение удаляемого элемента). Если запрос удаления вызывается на пустой очереди, то необходимо вывести −1.

Пример:
Ввод:

Вывод:

Я написал такой код на Python:

from queue import Queue

q = Queue()
min_q = Queue()
n = int(input())
result = []
temp = int(input())
q.put(temp); min_q.put(temp)
for _ in range(1, n):
    op = int(input())
    if op == 0:
        if q.empty(): result.append(-1)
        else:
            min_q.get()
            if min_q.empty(): min_q.put(q.get())
            else: q.get()
            result.append(min_q.queue[-1])
    else:
        if op < q.queue[-1]: min_q.put(op)
        else: min_q.put(q.queue[-1])
        q.put(op)
print(*result, sep="\n")

Но он выдаёт неверный ответ. Подскажите пожалуйста, в чём ошибка и как её исправить?

Answer 1

На "в чём ошибка и как её исправить?":

a) Исправьте две ошибки ниже, с ними ваша задача точно не пройдет тесты на граничные значения.

б) Потестируйте самостоятельно на граничных примерах. У вас элементариный минимальный тест не проходит.

в) Повторите на проверочной системе. Возможно, есть и еще ошибки, но без исправления этих их искать бессмыссленно.

г) Если тест все равно не пройдет, и не найдете новые ошибки сами, то откройте новый запрос тут.

Ошибка 1: у вас неверно задан range. При тестовом примере 1 0 он ни разу не сработает, а на вывод вместо -1 не выйдет ничего.

Рекомендация 1: исправить на range (n) (эквивалент range (0, n)).

Ошибка 2: у вас первый элемент ещё до цикла запоминается. При тестовом примере 1 0 даже при исправлении вышеописанной ошибки 1 код зависнет, ожидая ввода второго элемента.

Рекомендация 2: перенести ввод всех элементов в цикл, при необходимости скорректировать логику работу программы.

Answer 2

Ваше решение ошибается:

$ cat test3.txt 
4
1
2
3
0

$ python min_q.py < test3.txt
2

Должна быть единица в ответе. Видимо, у вас ошибка в алгоритме. Чтобы вам было легче тестировать, ниже решение в правильности которого сомнений нет - такое оно простое. Но оно не пройдёт по времени:

a = []
for _ in range(int(input())):
    v = int(input())
    if v > 0:
        a.append(v)
    else:
        if a:
            print(min(a))
            a.pop(0)
        else:
            print(-1)

P.S. Если вы добавите в вопрос ссылку на проверяющую систему, берусь помочь с правильным алгоритмом.

Answer 3

По-моему очень простая задачи.

Заранее говорю я никогда не изучал Python, не судите строго. Ваши притензий к коду с радостью прочитаю

P.S: Мне кажеться что ваш пример Ввода и Вывода не верный ?

print('Start')
n = int(input())
array = []
result = []
min = 10000

i = 1
while i <= n:
    ai = int(input())
    i += 1
    
    if ai > 0:
        if ai < min:
            min = ai
        array.append(ai)
        continue;
    
    if ai == 0:
        if len(array) != 0:
            array.pop()
            result.append(min)
        else:
            result.append(-1)

print('End')
print(*result, sep = '\n')

БЛОГ НА HUSL

Задача: "Очередь с поддержкой минимума"

Ответы (3 шт):