Ланч-бокси#165

Ланч-бокси (Editorial)

Кожна школа отримує або нуль, або рівно ланч-боксів, тому задача така: вибрати якнайбільше чисел k_i так, щоб їхня сума не перевищувала .

Тут працює проста жадібність: щоб взяти якнайбільше замовлень, вигідно починати з найменших.

Формально: нехай в оптимальному наборі з шкіл є якась школа, а поза набором — школа з меншим (або рівним) замовленням. Замінивши першу на другу, ми не збільшимо суму й не змінимо кількість шкіл. Повторюючи такі заміни, приходимо до набору з найменших замовлень. Отже, якщо взагалі можливо обслужити шкіл, то можливо обслужити саме найменших.

Розв'язок: відсортувати масив за зростанням, накопичувати префіксну суму й рахувати, скільки замовлень встигли додати, доки сума не перевищила . Щойно чергове додавання виводить суму за межу — зупиняємось і виводимо лічильник.

Складність — \mathcal{O}(M \log M) через сортування. Суму накопичуйте у 64-бітному типі, бо вона може помітно перевищити ще до зупинки.