Решение: Перевозка контейнеров
На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы. Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не меньше количества контейнеров, назначенных к перевозке. Какое максимальное количество контейнеров можно перевезти за один рейс и какова масса самого тяжёлого контейнера среди всех контейнеров, которые можно перевезти за один рейс?
В первой строке входного файла находятся два числа: $S$ — грузоподъёмность судна и $N$ — количество контейнеров. В следующих $N$ строках находятся значения масс контейнеров, требующих транспортировки, каждое в отдельной строке. Все числа натуральные; $S \leq 100\,000$, $N \leq 10\,000$, масса каждого контейнера не превышает 100.
Выведите два целых неотрицательных числа: максимальное количество контейнеров, которые можно перевезти за один рейс, и массу наиболее тяжёлого из них.
Решение по шагам
4 шагаДля максимального количества контейнеров выгодно выбирать самые лёгкие контейнеры: замена любого выбранного контейнера на более лёгкий не увеличивает суммарную массу.
Отсортируем массив масс по возрастанию.
$$m_1 \leq m_2 \leq \dots \leq m_N$$Будем последовательно складывать массы, пока очередной контейнер помещается на судно. Пусть $k$ — максимальный индекс, для которого сумма первых $k$ масс не превышает грузоподъёмность.
$$\sum_{i=1}^{k} m_i \leq S, \qquad \sum_{i=1}^{k+1} m_i > S$$Тогда можно перевезти $k$ контейнеров, а масса самого тяжёлого из них равна $m_k$.
Выводятся два значения: количество контейнеров $k$ и масса $m_k$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Выбирать контейнеры в исходном порядке, не сортируя их по массе.
Максимизировать суммарную массу вместо количества контейнеров.
Выводить массу следующего контейнера, который уже не помещается.