Задание 26 ЕГЭ по информатике: максимальное число грузов и масса самого тяжёлого

Решите задачу на выбор максимального числа грузов и наибольшую возможную массу одного из них.

Следующая задача в кабинете

Проверьте ответ здесь. Появится кнопка к другим заданиям этого номера.

К упражнениям
Скачать 26-gruzy.txt

При лимите 10 и массах 1, 2, 4, 7 вмещаются три груза. Набор 1, 2, 7 доказывает, что второй ответ равен 7.

Задания

1Авторская задача

В первой строке указаны грузоподъёмность машины и число грузов. Далее по строке на груз дана положительная целая масса. Каждый груз можно взять один раз. Найдите максимальное число грузов и наибольшую массу отдельного груза среди наборов такого размера. Грузоподъёмность можно исчерпать ровно.

Решение

Число грузов максимизируют самые лёгкие. После фиксации k оставляем k−1 самых лёгких и ищем самый тяжёлый подходящий из оставшихся. Любой другой набор из k−1 грузов весит не меньше этого префикса, поэтому замена покрывает все возможные максимальные массы.

from pathlib import Path
lines = Path("26-gruzy.txt").read_text().splitlines()
limit, n = map(int, lines[0].split())
a = sorted(map(int, lines[1:]))
assert len(a) == n
total = count = 0
for value in a:
    if total + value > limit:
        break
    total += value
    count += 1
prefix = sum(a[:count-1])
max_weight = max(value for value in a[count-1:] if prefix + value <= limit)
print(count, max_weight)

Дальше по теме

Источники