Интенсив по алгоритмам. Разбор ДЗ 3

Это Интенсив по алгоритмам в рамках Открытого лектория Академии Яндекса: academy.yandex.ru/lp/open-lec...
Записи лекций, по которым подготовлены задачи: yandex.ru/yaintern/algorithm-...
Ссылка на контест, который разбирается в этом видео: contest.yandex.ru/contest/401...

[@ozimandias1738]

Во второй задаче можно асимптотически лучшее решение найти - O(n). Единственный минус в том, что у нас 120*n (практически всегда хуже), так как придется завести массив на 121 элемент и потом на каждом шаге по нему итерироваться.

[@asqzan2359]

ty bro, keep going!

[@MrAnyTwo]

Объясните, пожалуйста, как получается выражение ans - (cnt - k) * minUs ?

[@TheZirkastu]

Мы ищем кол-во зелий при минимально допустимой полезности, может так оказаться что при такой полезности зелий больше чем нужно. Например получилось что 6 лучших зелий это зелья с полезностями 5 4 3 3 3 3. Здесь минимально допустимая полезность это 3. А нужно выбрать например всего k=3 лучших зелий поэтому из ответа вычитается полезность лишних зелий. Т.е в этом примере это три лишние тройки

[@MrAnyTwo]

​@@TheZirkastu А мы что, всегда будем получать последовательность полезностей, заканчиающейся цепочкой допустимых последовательностей в количестве не меньшем, чем (cnt - k) ? Мы не можем получить последовательность 8 6 5 4 3 3 ? Тут ведь при одборе 3х лучших останется 4 3 3 И уже на 3 умножать неправильно как-то.