7 Оптимальная упаковка: короткое правило
Оптимальная упаковка: короткое правило
Во всех задачах первого типа работает один и тот же приём, который легко держать в голове:
Свободные буквы всегда сажай в самые высокие (короткие) свободные ветки. Если букв больше, чем веток, — дели самую короткую ветку на две и продолжай. |
Именно поэтому:
одна свободная ветка длины
d+ нужно посадить 1 букву → код длиныd;одна свободная ветка длины
d+ нужно 2 буквы → делим её, получаем два кода длиныd + 1;две свободные ветки длины
d+ нужно 4 буквы → делим обе, четыре кода длиныd + 1.