26. Прикладная задача: Одну коробку можно поместить в другую, если длина её стороны хотя бы на 10…
В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $10$ единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Отсортируем длины сторон по возрастанию. Матрёшка — это цепочка, в которой каждая следующая коробка больше предыдущей хотя бы на $10$. Максимальную длину даёт обычная жадность: идём по возрастанию и берём коробку, если она подходит к последней взятой.
Со вторым вопросом жадность не справляется: она начинает с самой маленькой коробки, а нам нужна самая большая из возможных стартовых. Поэтому считаем для каждой коробки $ln[i]$ — длину максимальной цепочки, которая начинается именно с неё.
Тут работает удобное свойство: чем меньше коробка, тем длиннее цепочка от неё, потому что любую цепочку, начинающуюся с большей коробки, можно начать и с меньшей. Значит $ln$ не возрастает по мере роста стороны, и максимум среди подходящих продолжений достигается на самой первой коробке со стороной не менее $a_i + 10$. Её и находим двоичным поиском, а массив заполняем справа налево.
Затем берём $K$ — наибольшее значение в $ln$, и среди всех коробок с таким значением выбираем самую большую сторону.
from bisect import bisect_left
f = open('26-08.txt')
n = int(f.readline())
a = sorted(int(f.readline()) for _ in range(n))
ln = [1] * n # длина макс. цепочки, начинающейся с i-й коробки
for i in range(n-1, -1, -1):
j = bisect_left(a, a[i] + 10) # первая коробка, в которую влезет i-я
if j < n:
ln[i] = 1 + ln[j]
K = max(ln)
smallest = max(a[i] for i in range(n) if ln[i] == K)
print(K, smallest) # 935 51
Проверка. В файле $10000$ коробок со сторонами от $50$ до $9998$, жадный подсчёт тоже даёт цепочку из $935$ коробок. Файл тот же, что в задаче с разницей $3$, где ответ был $2767$ и $51$: при более жёстком шаге цепочка ожидаемо укоротилась почти втрое, а стартовая коробка осталась прежней. На типовом примере из условия с разницей $3$ программа выдаёт $3$ и $32$.