Московская олимпиада по информатике - 2005: различия между версиями
Содержимое удалено Содержимое добавлено
Опечатка "использующее только кучк свободных тупиков" |
|||
Строка 577:
Как же устроена priority_queue изнутри и насколько быстро выполняются требуемые операции? Для хранения элементов в очереди с приоритетами используется ''куча - ''бинарное дерево, элементы которого расположены специальным образом. Наименьший элемент находится в вершине дерева, а добавление и удаление элемента в куче выполняются за логарифм от общего числа элементов. Таким образом, наше решение будет иметь сложность порядка ''N'' log (''N+K''). Подробнее об этой структуре данных можно прочитать, например, в книге Т. Кормена и др. "Алгоритмы: построение и анализ". Обратите внимание, что ограничения на количество тупиков и количество электричек таковы, что при использовании вместо кучи массива или списка решение будет иметь сложность ''N''(''N+K''), и не будет работать на больших тестах за указанное время.
Существует также решение, использующее только
[[Категория:Программирование]]
|