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

@Dialoss · Регистрация: 30.05.2020

Студворк — интернет-сервис помощи студентам

Здравствуйте, стоит задача написать очередь с поддержкой минимума.

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

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

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

На каждый запрос удаления элемента из очереди необходимо вывести значение минимального элемента очереди (учитывая значение удаляемого элемента). Если запрос удаления вызывается на пустой очереди, то необходимо вывести −1.

Вот мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque
dek = deque()
output = [] # массив можно было не создавать, но мне так легче для восприятия вывода
 
x = int(input()) # кол-во операций
while x:
    n = int(input()) 
    if n > 0:
        dek.append(n)
 
    else:
        if len(d) > 0:
            minimum = min(dek)
            num = dek.popleft() # число, которое мы достаем из дека
            if minimum == num:
                output.append(num)
 
            elif num > minimum:
                output.append(minimum)
 
        else:
            output.append("-1")
    x -= 1
 
for i in output:
    print(i)

Для этого я использую встроенную структуру "дек", но программа не проходит по времени, хотя работает корректно.
Перед удалением из очереди элемента, я записываю в переменную его значение, чтобы не потерять, в другую записываю минимум и сравниваю эти два значения: если число и минимум равны, то в вывод попадает само число, а если число больше минимума, то минимум.
Подскажите, где я ошибся

@err · 19.06.2020, 14:35

Возможно стоит попробовать сначала найти минимум, а потом удалить элемент из очереди

Python
1
2
3
4
5
        if len(queue)>0:
            prot.append(min(queue))
            queue.pop(0)
        else:
            prot.append(-1)

Рыжий Лис · 19.06.2020, 15:55

Python
1
2
3
4
5
6
7
8
9
10
11
12
ls = [1,2,32,0,34,0,4,0,0,0,0,0,0,0,12,1,1,3,4,0]
 
stack = []
for i in ls:
    if i == 0:
        if stack:
            print(min(stack))
            j = stack.pop(0)
        else:
            print(-1)
    else:
        stack.append(i)

@Dedkrut · 20.06.2020, 15:46

Рыжий Лис, Мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
queue = []
for i in range(int(input())):
    a=int(input())
    if a>0:
        queue.append(a)
    elif a==0:
        if len(queue) == 0:
            print('-1')
        else:
            print(min(queue))
            queue.pop(0)

Очень схож с вашим, но не проходит по времени

, как так может быть?

Рыжий Лис · 20.06.2020, 16:01

А мой код проходит?

Отличие в одном лишнем if'е и в другом if'e ветви переставлены - предсказатель ветвлений может ошибаться... но это ведь не с++ и не jit...

@Dedkrut · 20.06.2020, 16:06

Рыжий Лис, вот этот тоже не проходит

Python
1
2
3
4
5
6
7
8
9
10
11
queue = []
for i in range(int(input())):
    n=int(input())
    if n == 0:
        if queue:
            print(min(queue))
            queue.pop(0)
        else:
            print(-1)
    else:
        queue.append(n)

@Voooolodia · 20.06.2020, 16:08

Вот мой код. Но он тоже не проходит по времени. Операция удаления 1-ого элемента делается слишком долго - за O(n). Поэтому я создал переменную const и при удалении стал добавлять к ней единицу, а поиск минимума делаю в срезе "const:".

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def main():
    a = int(input())
    och = []  # сама очередь
    res = []  # результат
    const = 0
    for i in range(a):
        b = int(input())
        if b > 0:
            och.append(b) # добавляем в очередь b если b > 0
        elif b == 0 and len(och) != const : # если b = 0 и кол-во элементов в очереди не равно кол-ву "зачёркнутых элементов"
            res.append(min(och[const:]))
            const += 1
        elif b == 0 and len(och) == const:
            res.append('-1')
    for i in res:
        print(i) # вывод по одной цифре в троке
main()

Рыжий Лис · 20.06.2020, 16:23

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
 
ls = [1,2,32,0,34,0,4,0,0,0,0,0,0,0,12,1,1,3,4,0]
 
stack = []
m = sys.maxsize  # минимум
for i in ls:
    if i != 0:
        stack.append(i)
        if i < m:
            m = i
        continue
        
    if not stack:  # o(1)
        print(-1)
        continue
 
    print(m)
    j = stack.pop(0)
    if j == m:
        # ой, не повезло, пересчитываем
        m = min(stack) if stack else sys.maxsize

Добавлено через 2 минуты
Voooolodia прав, лучше взять collections.deque

append O(1)

pop O(1)

popleft O(1)

Добавлено через 3 минуты

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import deque
 
ls = [1,2,32,0,34,0,4,0,0,0,0,0,0,0,12,1,1,3,4,0]
 
r = deque()
for i in ls:
    if i != 0:
        r.append(i)    # o(1)
        continue
    if not r:
        print(-1)
        continue
    print(min(r))  # o(n)
    j = r.popleft()  # o(1)

@Eshkin_Kot · 21.06.2020, 14:58

Код рабочий.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
st = [] 
st2 = [] 
mn = [] #Поддержание минимума в 1 стеке
mn2 = []#Поддержание минимума во 2 стеке
 
def push(a):
    global st
    global mn
    st.append(a)
    if  not mn or a < mn[-1]:
        mn.append(a)
    else:
        mn.append(mn[-1])
 
def get_min():
    global st
    global st2
    global mn
    global mn2
    if not st2 and st:
        for i in range(len(st)):       
            if  not mn2 or st[-1] < mn2[-1]:
                mn2.append(st[-1])
            else:
                mn2.append(mn2[-1])
            st2.append(st.pop())
        st =[]
        mn = []
    if not st2 and not st:
        print(-1)
    elif mn:
        st2.pop()
        print(min(mn[-1], mn2.pop()))
    else:
        st2.pop()
        print(mn2.pop())
 
 
for k in range(int(input())):
    a = int(input())
    if a != 0:
        push(a)
    else:
        get_min()

@little_Ganter · 10.08.2021, 13:42

Eshkin_Kot, не мог бы ты объяснить алгоритм, я пишу на с++ и твоё решение не могу понять, заранее благодарен

@simpotyga · 03.10.2021, 19:34

Eshkin_Kot, уже не рабочий(

@Z_Dim_V · 29.05.2022, 13:59

Код, который предложил Eshkin_Kot, рабочий, но есть проблема с выводом результатов в соответствии с условием задания. Код, который проходит проверку на Сириусе таков:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
st = []
st2 = []
mn = []  # Поддержание минимума в 1 стеке
mn2 = []  # Поддержание минимума во 2 стеке
res = []  # Результаты операций для вывода ответа
 
 
def push(a):
    global st
    global mn
    st.append(a)
    if not mn or a < mn[-1]:
        mn.append(a)
    else:
        mn.append(mn[-1])
 
 
def get_min():
    global st
    global st2
    global mn
    global mn2
    if not st2 and st:
        for i in range(len(st)):
            if not mn2 or st[-1] < mn2[-1]:
                mn2.append(st[-1])
            else:
                mn2.append(mn2[-1])
            st2.append(st.pop())
        st = []
        mn = []
    if not st2 and not st:
        res.append(-1)
    elif mn:
        st2.pop()
        res.append(min(mn[-1], mn2.pop()))
    else:
        st2.pop()
        res.append(mn2.pop())
 
 
for k in range(int(input())):
    a = int(input())
    if a != 0:
        push(a)
    else:
        get_min()
print(*res, sep='\n')

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

Рыжий Лис Просто Лис 5972 / 3734 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	20.06.2020, 16:01
	А мой код проходит? Отличие в одном лишнем if'е и в другом if'e ветви переставлены - предсказатель ветвлений может ошибаться... но это ведь не с++ и не jit... 0

@little_Ganter 0 / 0 / 0 Регистрация: 28.06.2021 Сообщений: 12
	10.08.2021, 13:42
	Eshkin_Kot, не мог бы ты объяснить алгоритм, я пишу на с++ и твоё решение не могу понять, заранее благодарен 0

@simpotyga 7 / 7 / 0 Регистрация: 04.12.2020 Сообщений: 40
	03.10.2021, 19:34
	Eshkin_Kot, уже не рабочий( 0