Войти Регистрация
Алгоритмы

188. Склеить логи с минимумом записи на диск

Средняя

За ночь сервис сообщений VK оставил n файлов логов, sizes[i] — размер i-го в мегабайтах. Файлы нужно собрать в один.

За шаг склеиваются любые два файла; на диск при этом пишется новый файл размером в их сумму. Найдите наименьший суммарный объём записи, после которого останется один файл. Для одного файла ответ 0.

В работе: На узле архивации 4000 файлов от 1 до 900 МБ, а запись на диск ограничена: разница между порядком «подряд» и лучшим порядком — сотни гигабайт за ночь.

Пример 1

Ввод
sizes = [40, 10, 30, 20]
Вывод
190

10 + 20 = 30, 30 + 30 = 60, 60 + 40 = 100: всего 190 МБ.

Пример 2

Ввод
sizes = [500]
Вывод
0

Склеивать нечего.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ sizes[i] ≤ 10⁴
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def merge_cost(sizes):
КучаЖадный алгоритмКод ХаффманацельO(n log n)

Источник: наша задача на данных VK. Условие пересказано своими словами.