Заводится структура данных под названием очередь по приоритетам, проще всего - на основе кучи (heap, бинарная пирамида) на к элементов. В нее заносятся первые k элементов из списка, затем каждый следующий сравнивается с максимальным текущим элементом (вершиной кучи), и если он меньше, заменяется вершина кучи и выполняется восстановление пирамидальности кучи.
Очередь по приоритетам можно сделать и на основе второго списка - он сортирован, максимальный элемент в голове. Если очередной элемент меньше головы, она удаляется, а элемент вставляется в нужное место списка. Этот метод проще, но медленнее работает, хотя для учебной задачи это, наверно, неважно. |
