Московская олимпиада по информатике - 2005: различия между версиями

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