2

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

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

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

9  
5  
4  
3  
6  
0  
0  
0  
0  
0  

Вывод:

3  
3  
3  
6 
-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")

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

8
  • 1) В чем логика if op < q.queue[-1]: min_q.put(op) else: min_q.put(q.queue[-1])? 2) почему вообще что-то в одну строку через:? 22 июл 2022 в 10:23
  • Во второй очереди для каждого из элементов первой я храню минимальный. Когда из первой очереди удаляется элемент, из второй удаляется соответствующий ему минимальный элемент. Т.е. если введённое значение меньше, чем минимум из предыдущих, то оно добавляется во вторую очередь. иначе в неё добавляется прошлый минимум
    – Thwrani
    22 июл 2022 в 10:31
  • Ответ, который я получил при запуске: 3, 3, 3, 6, -1. Чем он неправильный? Первые три элемента имеют минимумом 3, затем последний 6 - сам себе минимум, последний 0 вызывает -1. 22 июл 2022 в 10:43
  • @Сергей, Ответ из примера сходится, но этот код не проходит какой-то из тестов. Входные данные мне не известны...
    – Thwrani
    22 июл 2022 в 10:46
  • @StanislavVolodarskiy, а из очереди не надо ничего выводить. Надо выводить минимум на момент запроса на удаление. "необходимо вывести значение минимального элемента очереди". А это три раза 3. 22 июл 2022 в 10:46

3 ответа 3

1

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

Заранее говорю я никогда не изучал 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')
7
  • 4 1 2 0 0 должен выдать 1 2. Ваша программа выдаст 1 1. 22 июл 2022 в 12:40
  • Производительность вашей программы недостаточна. Для миллиона чисел она будет тормозить. Можно написать быстрее. 22 июл 2022 в 12:43
  • @StanislavVolodarskiy ну да, при удалений элемента она должна показывать минимальное значение из очередь, или нет?
    – Miha
    22 июл 2022 в 12:44
  • На каждый запрос удаления элемента из очереди необходимо вывести значение минимального элемента очереди
    – Miha
    22 июл 2022 в 12:46
  • Добавили 1 и 2 в очередь, получили [1, 2]. Удалили, получили [2]. Удалили, получили []. Последний минимум должен быть 2 потому что в очереди в этот момент только один элемент - двойка. 22 июл 2022 в 12:46
0

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

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

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

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

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

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

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

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

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

1
  • Если ответ был полезным, его можно отметить плюсом (нажать треугольник вверх слева от вопроса). Если ответ решил задачу - принять ответ (нажать на галку под треугольниками слева). Можно и то, и другое 22 июл 2022 в 11:02
-1

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

$ 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. Если вы добавите в вопрос ссылку на проверяющую систему, берусь помочь с правильным алгоритмом.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.