2 / 2 / 0
Регистрация: 30.05.2020
Сообщений: 10
1

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

18.06.2020, 10:47. Показов 23648. Ответов 11

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

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

Первая строка входных данных содержит число 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)
Для этого я использую встроенную структуру "дек", но программа не проходит по времени, хотя работает корректно.
Перед удалением из очереди элемента, я записываю в переменную его значение, чтобы не потерять, в другую записываю минимум и сравниваю эти два значения: если число и минимум равны, то в вывод попадает само число, а если число больше минимума, то минимум.
Подскажите, где я ошибся
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.06.2020, 10:47
Ответы с готовыми решениями:

Очередь с поддержкой минимума
Помогите, пожалуйста, моя программа не проходит проверку, выдаёт ошибку в процессе выполнения. ...

Очередь с поддержкой минимума
Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума. Входные данные ...

Очередь с поддержкой минимума.Линейные структуры данных. Python
Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума. Входные данные ...

Очередь с поддержкой минимума
Здравствуйте, уважаемые знатоки. Я - мама начинающего программера. Дочь бьётся над этими двумя...

11
19 / 15 / 4
Регистрация: 07.04.2020
Сообщений: 63
19.06.2020, 14:35 2
Возможно стоит попробовать сначала найти минимум, а потом удалить элемент из очереди
Python
1
2
3
4
5
        if len(queue)>0:
            prot.append(min(queue))
            queue.pop(0)
        else:
            prot.append(-1)
0
Просто Лис
Эксперт Python
5716 / 3517 / 1053
Регистрация: 17.05.2012
Сообщений: 10,338
Записей в блоге: 9
19.06.2020, 15:55 3
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)
1
5 / 4 / 1
Регистрация: 23.05.2020
Сообщений: 22
20.06.2020, 15:46 4
Рыжий Лис, Мой код:
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)
Очень схож с вашим, но не проходит по времени , как так может быть?
0
Просто Лис
Эксперт Python
5716 / 3517 / 1053
Регистрация: 17.05.2012
Сообщений: 10,338
Записей в блоге: 9
20.06.2020, 16:01 5
А мой код проходит?

Отличие в одном лишнем if'е и в другом if'e ветви переставлены - предсказатель ветвлений может ошибаться... но это ведь не с++ и не jit...
0
5 / 4 / 1
Регистрация: 23.05.2020
Сообщений: 22
20.06.2020, 16:06 6
Рыжий Лис, вот этот тоже не проходит
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)
0
62 / 1 / 0
Регистрация: 20.06.2020
Сообщений: 3
20.06.2020, 16:08 7
Вот мой код. Но он тоже не проходит по времени. Операция удаления 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()
1
Просто Лис
Эксперт Python
5716 / 3517 / 1053
Регистрация: 17.05.2012
Сообщений: 10,338
Записей в блоге: 9
20.06.2020, 16:23 8
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)
1
7 / 7 / 0
Регистрация: 21.06.2020
Сообщений: 1
21.06.2020, 14:58 9
Код рабочий.


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()
7
0 / 0 / 0
Регистрация: 28.06.2021
Сообщений: 12
10.08.2021, 13:42 10
Eshkin_Kot, не мог бы ты объяснить алгоритм, я пишу на с++ и твоё решение не могу понять, заранее благодарен
0
6 / 6 / 0
Регистрация: 04.12.2020
Сообщений: 40
03.10.2021, 19:34 11
Eshkin_Kot, уже не рабочий(
0
1 / 1 / 0
Регистрация: 28.05.2022
Сообщений: 1
29.05.2022, 13:59 12
Код, который предложил 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')
1
29.05.2022, 13:59
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.05.2022, 13:59
Помогаю со студенческими работами здесь

Очередь с поддержкой минимума
Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума. Входные данные ...

Очередь с поддержкой минимума
Реализуйте очередь с поддержкой минимума. Входные данные Первая строка входных данных...

Очередь с поддержкой минимума
Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума. Входные данные ...

Очередь с поддержкой минимума
Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума. Входные данные ...

Очередь с поддержкой минимума, почему то не проходит по времени
Очередь с поддержкой минимума Реализуйте очередь с поддержкой минимума. Входные данные ...

очередь с приоритетом, извлечение минимума
сабж http://www.cplusplus.com/reference/stl/priority_queue по умолчанию там есть только метод...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru