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

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

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

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

   C++

   #include <iostream> using namespace std; struct Node { string id; int priority; Node* next; Node(string _id = "", int _priority = 0, Node * _next = nullptr) { id = _id; priority = _priority; next = _next; } }; struct PriorityQueue { Node *first; PriorityQueue() {first = nullptr;} void add(string _id, int _priority) { Node *i = first; if(first == nullptr || _priority > first->priority) { first = new Node(_id, _priority, first); } else { while (i->next != nullptr && _priority < i->next->priority) i = i->next; i->next = new Node(_id, _priority, i->next); } } void erase(string _id) { Node *res = first; if (first->id == _id) { first = first->next; } else { Node *i = first; while(i->next->id != _id) i = i->next; res = i->next; i->next = res->next; } delete res; } void change(string _id, int _priority) { erase(_id); add(_id, _priority); } void pop() { Node * tmp = first; first = tmp->next; delete tmp; } }; int main() { PriorityQueue q; string command, id; int prio; while (cin >> command) { if (command == "ADD") { cin >> id; cin >> prio; q.add( id, prio); } if (command == "CHANGE"){ cin >> id; cin >> prio; q.change( id, prio ); } if (command == "POP") { cout << q.first->id << " " << q.first->priority << endl; q.pop(); } } return 0; }

   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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

   #include <iostream>   using namespace std;   struct Node { string id; int priority; Node* next; Node(string _id = "", int _priority = 0, Node * _next = nullptr) {    id = _id; priority = _priority; next = _next; } };   struct PriorityQueue { Node *first; PriorityQueue() {first = nullptr;} void add(string _id, int _priority) { Node *i = first; if(first == nullptr || _priority > first->priority) { first = new Node(_id, _priority, first); } else { while (i->next != nullptr && _priority < i->next->priority) i = i->next; i->next = new Node(_id, _priority, i->next); } } void erase(string _id) { Node *res = first; if (first->id == _id) { first = first->next; } else { Node *i = first; while(i->next->id != _id) i = i->next; res = i->next; i->next = res->next; } delete res; } void change(string _id, int _priority) { erase(_id); add(_id, _priority); } void pop() { Node * tmp = first; first = tmp->next; delete tmp; } };   int main() {    PriorityQueue q;    string command, id;    int prio;    while (cin >> command) {      if (command == "ADD") {          cin >> id;          cin >> prio;          q.add( id, prio);        }        if (command == "CHANGE"){          cin >> id;          cin >> prio;          q.change( id, prio );        }        if (command == "POP") {          cout << q.first->id << " " << q.first->priority << endl;          q.pop();        }    }    return 0; }

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

   Войдите, чтобы ответить

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

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

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

   Войдите, чтобы ответить

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

   Войдите, чтобы ответить

   • Видимо, я неправильно Вас понял. Если тесты проходят (а они теперь проходят), то ничего делать больше не нужно.