Сортировка различных строк

Question

Я застрял в этой проблеме. Может кто-то, пожалуйста, помогите мне решить это?

Нам даны n отсортированных линий людей с длиной l1, l2, ..., ln. Строки отсортированы по высоте. Мы хотим объединить все строки в одну отсортированную строку. Мы можем объединить 2 строки за раз, что требует времени, которое пропорционально количеству людей в обеих линиях.

Создайте алгоритм, в котором мы можем выбрать лучший порядок для объединения всех строк в течение как можно меньшего количества времени.

Answer 1

Рассмотрим жадный алгоритм:

while line number > 1: 
    take the shortest two lines li, lj 
    merge them 

Является ли это оптимальным решением? Вы видите, что следующие факты верны:

• , если вы знаете, дерево слияния (то есть дерево, которое говорит вам, что были объединены пары линий и когда (глубже элемент объединены первым и дерево читаются слева направо)), мы видим, что оптимальным решением является тот, в котором линии с малой длиной имеют большую глубину. Мы можем начинать с листьев, заполняя дерево, снизу вверх, с длиной линий, отсортированной в порядке возрастания.
• , что означает наименьшие две линии на листьях
• изменяющих порядок листа не меняется оптимальное решение
• мы можем изменить порядок наименьшие линии, чтобы быть первым двух Лифс Итак, мы нашли оптимальное решение в который мы выбираем, объединяют две линии с наименьшей длиной. По индукции мы можем продолжать это.

Вы можете реализовать этот алгоритм с использованием очереди с минимальным приоритетом.

initialize min-priority queue q  
insert all line lengths in q 
ans = 0 
while q > 1: 
    a = q.pop() 
    b = q.pop() 
    ans += a+b 
    q.push(a+b) 
return ans