1

Входные данные

Первая строка входных данных содержит число 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

Написал код, реализующий очередь через 2 стека(на одном из них поддержка минимума), но система выдаёт неверный результат работы программы, в чём проблема?

def push(stack,stack_min,elem):
    stack.append(elem)
    if stack_min and stack_min[-1] < elem:
        stack_min.append(stack_min[-1])
    else:
        stack_min.append(elem)

s1=[]
s2=[]
s2min=[]
n=int(input())
a=0
for i in range(n):
    a=int(input())
    if a>0:
        s1.append(a)
    else:
        for j in range(len(s1)):
            push(s2,s2min,s1[-1])
            s1.pop()
        if s2min:
            print(s2min[-1])
            s2min.pop()
        else:
            print(-1)
0

2 ответа 2

1

Чуть-чуть надо поменять код. Такой:

if s2min:
    print(s2min[-1])
    s2min.pop() # это надо передвинуть
else:
    print(-1)

На такой:

s2min.pop() # сначала удаляем элемент, а потом уже делаем проверку и печать
if s2min:
    print(s2min[-1])
else:
    print(-1)
    

Вывод:

3
3
3
6
-1
2
  • С минимумом только на одном стеке решение не может работать. 29 мар в 14:37
  • @StanislavVolodarskiy 4 года назад дело было, это мне заново нужно задачку вспоминать )
    – CrazyElf
    29 мар в 14:45
0

Ошибка

Рассмотрим ввод:

6
10
1
0
10
0
0

Соотвествующий вывод:

1
1
1

Последнее число должно быть 10, потому что в очереди осталость только одно число - последняя десятка. Ваша программа печатает 1. Причина - структура в вашей программе - не очередь, порядок элементов нарушается.

Чтобы из двух стеков построить очередь, надо соблюдать правило: перенос элементов между стеками начинается только тогда когда второй стек пуст. Иначе порядок нарушится. Раз так, то при удалении элемента оба стека могут быть не пусты и текущий минимум нужно искать в обоих стеках.

Решение длинное и правильное

ООП решение, которое не срезает углы и определяет универсальные стек и очередь, выглядит так:

class Stack:
    def __init__(self):
        self._stack = []

    def __bool__(self):
        return bool(self._stack)

    def push(self, v):
        self._stack.append((v, min(v, self.min()) if self._stack else v))

    def pop(self):
        return self._stack.pop()[0]

    def min(self):
        return self._stack[-1][1]


class Queue:
    def __init__(self):
        self._stack1 = Stack()
        self._stack2 = Stack()

    def __bool__(self):
        return bool(self._stack1) or bool(self._stack2)

    def push(self, v):
        self._stack1.push(v)

    def pop(self):
        if not self._stack2:
            while self._stack1:
                self._stack2.push(self._stack1.pop())
        return self._stack2.pop()

    def min(self):
        return min(s.min() for s in (self._stack1, self._stack2) if s)


def main():
    q = Queue()
    for _ in range(int(input())):
        a = int(input())
        if a > 0:
            q.push(a)
        else:
            print(q.min() if q else -1)
            if q:
                q.pop()


main()

Решение короткое олимпиадное

Если отказаться от чёткого следования принципам ООП, код будет в три раза короче:

s1 = []     # первый стек хранит только значения без минимумов
s1_min = [] # [min(s1)] if s1 else [] : текущий минимум первого стека целиком
s2 = []     # второй стек хранит только минимумы без значений
for _ in range(int(input())):
    a = int(input())
    if a > 0:
        s1.append(a)
        s1_min = [min([a] + s1_min)]
    else:
        print(min(s1_min + s2[-1:], default=-1)) # минимум по обоим стекам
        if not s2:
            while s1:
                s2.append(min([s1.pop()] + s2[-1:]))
            s1_min = []
        if s2:
            s2.pop()

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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