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