7 Оптимальная упаковка: короткое правило

Оптимальная упаковка: короткое правило

Во всех задачах первого типа работает один и тот же приём, который легко держать в голове:

Свободные буквы всегда сажай в самые высокие (короткие) свободные ветки. Если букв больше, чем веток, — дели самую короткую ветку на две и продолжай.

Именно поэтому:

  • одна свободная ветка длины d + нужно посадить 1 букву → код длины d;

  • одна свободная ветка длины d + нужно 2 буквы → делим её, получаем два кода длины d + 1;

  • две свободные ветки длины d + нужно 4 буквы → делим обе, четыре кода длины d + 1.