Задание 26 ЕГЭ по информатике: Сортировка и жадный выбор. Тренировочная версия: данные приведены в условии, ответ — целое число.
Подсказка: Разбери условие по шагам: отдельно запиши промежуточные значения (подсчёт, суммы, остатки). Ответ — целое число.
Примеры с разбором
Пример 1
На складе лежат 10 посылок, массы (кг) указаны в списке. Грузовик увозит посылки общей массой не более 96 кг. Какое наибольшее количество посылок он может увезти?
7 31 51 20 60 14 34 46 16 31
Ответ: 5
Решение: Жадный выбор: бери самые лёгкие посылки по порядку, пока сумма не превысит предел.
Пример 2
Бюджет покупателя — 173 руб.; цены 10 товаров (в рублях) указаны в списке. Он покупает товары по возрастанию цены, пока хватает денег. Какова цена последнего купленного товара?
9 34 16 28 51 35 15 40 34 19
Ответ: 34
Решение: Отсортируй цены по возрастанию и накапливай сумму, пока она не превысит бюджет.
Пример 3
Бюджет покупателя — 130 руб.; цены 10 товаров (в рублях) указаны в списке. Он покупает товары по возрастанию цены, пока хватает денег. Какова цена последнего купленного товара?
36 37 38 19 16 6 23 18 18 50
Ответ: 23
Решение: Отсортируй цены по возрастанию и накапливай сумму, пока она не превысит бюджет.