Фотографии на память

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

Далее, если хотим делать динамическое программирование, до делаем массив $$$dp[n]$$$ — минимальное число фотографий, которое нужно сделать, чтобы сфотографировать первых $$$n$$$ существ. Тогда:

Также можно довериться интуиции или доказать, что всегда выгодно брать на каждую следующую фотографию, как можно больше существ. Тогда, если $$$n$$$ существ, уже сфотографированы, смотрим следующих трех, если можно их разместить на одной фотографии, то размещаем и переходим к $$$n + 3$$$, если нет, пытаемся взять двух, если и тут нет, берем одного.

Независимо от выбора решения, асимптотическая сложность будет $$$O(n)$$$.