e-olimp 4847. Очередь с приоритетами

Условие: Реализуйте структуру «очередь с приоритетами», поддерживающую следующие операции:

  1. Добавление элемента в очередь.
  2. Удаление из очереди элемента с наибольшим приоритетом.
  3. Изменение приоритета для произвольного элемента, находящегося в очереди.

Тесты:

input data output data
add eight 8 <вывод не предусмотрен>
add three 3 <вывод не предусмотрен>
add eleven 11 <вывод не предусмотрен>
add one 1 <вывод не предусмотрен>
add five 5 <вывод не предусмотрен>
add neun 9 <вывод не предусмотрен>
add forteen 14 <вывод не предусмотрен>
add six 6 <вывод не предусмотрен>
add ten 10 <вывод не предусмотрен>
add twelve 12 <вывод не предусмотрен>
add fifteen 15 <вывод не предусмотрен>
add seven 7 <вывод не предусмотрен>
add thirteen 13 <вывод не предусмотрен>
change eleven 1100 <вывод не предусмотрен>
change eleven 1101 <вывод не предусмотрен>
change one 111 <вывод не предусмотрен>
pop eleven 1101
pop one 111
pop fifteen 15
pop forteen 14
pop thirteen 13
pop twelve 12
pop ten 10
pop neun 9
pop eight 8
pop seven 7
pop six 6
pop five 5
pop three 3
pop error

Код программы:

Компилировать под Gnu C++ 4.7.1

План программы:

При решении задачи учитывалась необходимость быстрого поиска по двум независимым параметрам — ид и приоритета.

Задача решалась в два этапа, сначала был написан вариант с упорядоченным списком, который позволял мгновенный pop, но add и change не удовлетворили тестам на скорость т.к. основывались на поиску путем перебора. Было приято решение использовать алгоритм поиска в двоичном дереве, учитывая, что условия задачи позволяли большой объем памяти.

 

Текущий вариант основывается шаблонном классе, реализующем двоичное дерево. Очередь содержит два объекта – дерево со строковыми ключами для хранения Id и дерево с числовыми ключами для хранения приоритетов. Каждый узел дерева Id указывает на узел дерева приоритетов. Это позволяет немедленно получить приоритет данного Id без поиска, что необходимо для операции change. В свою очередь, каждый узел дерева приоритетов указывает на узлы дерева Id с данным приоритетом. Это позволяет немедленно определить какой Id надо удалять при выполнении pop. Для обслуживания нескольких Id с равным приоритетом пришлось ввести еще один шаблонный класс – список.

 

Краткое описание операций

  • Add
    1. Находим или добавляем узел дерева Id (ситуацию если он есть игнорируем по условию задачи)
    2. Находим или добавляем узел дерева приоритетов
    3. Для узла дерева Id устанавливаем указатель на узел дерева приоритетов
    4. Для узла дерева приоритетов добавляем в его список узел дерева Id

 

  • Pop
    1. Находим узел дерева приоритетов с максимальным ключом
    2. Удаляем из списка найденного узла первый попавшийся указатель на узел дерева Id, если список
    3. Если список уже пуст, удаляем узел дерева приоритетов

 

  • Change
    1. Находим узел дерева Id (ситуацию если его нет игнорируем по условию задачи)
    2. Берем узел дерева приоритетов, на который указывает узел Id и удаляем из его списка этот узел Id (т.к. приоритет уже будет новый), если список оказался пуст, удаляем также узел приоритета
    3. Находим или добавляем узел дерева приоритетов с новым приоритетом и устанавливаем связь с узлом Id как в случае добавления.

 

Ссылка: http://ideone.com/FROADt

Швандт Максим Альбертович
Швандт Максим Альбертович

Latest posts by Швандт Максим Альбертович (see all)

6 thoughts on “e-olimp 4847. Очередь с приоритетами

  1. Результат по тестам e-olimp:

    • 1 — 13: Неверный ответ
    • 14 — 17: Исчерпан лимит времени

    Неверные ответы объясняются выводом «ok», которого не должно быть. А вот с временем работы нужно как следует подумать. Если выбросить все лишнее, то пройдут еще два теста:

    Операции ADD и CHANGE в Вашем связном списке работают медленно — за линейное время O(n). Операция удаления максимума — быстро — O(1). Т.е. две из трех операций тормозят. Вам нужно сильно ускорить поиск по идентификатору и поиск по приоритету. Это поможет сделать, например, бинарная куча, которую мы изучали.
    Лучше ее сделать параметризованной (template), чтобы ускорить обе операции.

    • Я переделал и добился таких же результатов, как и предложенный вами пример – только 2 случая -16, 17 – исчерпали лимит времени. Также мне пришлось убрать полезную проверку на присутствие элементов в add. Очевидно, устранить это можно только введением двоичного поиска, но у меня возникла проблема, что я не могу его использовать со списком, на чём основана ваша и моя очередь. Двоичный поиск применяется там, где элемент доступен непосредственно по индексу, а в списке я должен всё время перебирать элементы, чтобы найти нужный. Означает ли это, что я должен использовать массив вместо списка? Это приведёт к существенной переделке кода и ограничению на размер.

      • Если в условии написано «Гарантируется, что в очереди нет элемента с таким идентификатором», то почему Вы считаете полезной перепроверку этого условия? Какие осмысленные действия может выполнить программа, уличившая автора задачи в обмане?

  2. Отказываться от списков нет никакой необходимости. Нужно придумать такую реализацию, чтобы требуемые операции ADD, POP и CHANGE работали как можно быстрее. В идеале время их работы не должно зависеть от количества элементов в очереди. Вполне подойдет если некоторые из них будут иметь логарифмическую сложность. Если сложность хоть одной из указанных операций становится линейной, решение не имеет шансов отработать за отведенное время.
    Посчитайте, какова сложность Ваших алгоритмов?

  3. Я тестировал программу на довольно длинных последовательностях, где я сам мог ошибиться и не гарантировать этого условия задачи, поэтому я добавил эту проверку, чтобы проверить свои собственные тесты, где я мог ошибиться и допустить не уникальность. Затем, после того, как на Е-олимпе тесты на скорость прошли, даже с этой проверкой, я предпочел ее не убирать во избежании внесения новых ошибок, а я боюсь, что не успею отладить программу в срок снова.
    Что касается списков, мой предыдущий вариант, был выполнен на основании вашего примера, который вы мне прислали , но он не проходил последние 2 теста на скорость. Кстати, я проверил ваш пример — он тоже не проходил именно эти 2 теста. По-этому я нашел ваш совет использовать деревья бинарного поиска единственно возможными., тем более что по условию задачи разрешается использовать очень много памяти — 64 МБ, что является намеком на разрешение использовать всяческие вспомогательные структуры данных, ускоряющие поиск. И, действительно, применение деревьев бинарного поиска по Вашему совету спасло ситуацию — теперь все тесты проходят. Если надо, я прикреплю предыдущий вариант программы, но он не удовлетворяет по производительности, как я уже говорил.

Добавить комментарий