Задание 26 ЕГЭ по информатике: сортировка и жадные алгоритмы — разбор и примеры

Задание 26 — обработка большого набора данных из файла. Сюжеты разные: загрузка грузов в машину, размещение файлов на диске, распределение заявок на зал, продажа товаров со скидками, рассадка зрителей по рядам. Но почти всегда решение строится по одной схеме: отсортировать данные и затем делать локально лучший выбор на каждом шаге. Такой подход называется жадным алгоритмом. Ответ обычно состоит из двух чисел: основная величина (например, наибольшее количество объектов) и дополнительная (например, наибольший возможный размер самого большого из выбранных).

Что проверяет задание

• умение прочитать файл: в первой строке параметры (вместимость, количество записей), дальше по одной записи в строке;
• знание сортировки и умение выбрать правильный ключ сортировки;
• понимание, почему жадный выбор даёт оптимум именно в этой задаче, и умение отличить случаи, где он не работает;
• аккуратность со второй частью вопроса: она часто требует отдельного шага после основного жадного прохода.

Типичные формулировки

1. «Найдите максимальное количество предметов, которые можно погрузить, и максимальную массу самого тяжёлого предмета среди всех таких наборов».
2. «По заявкам на проведение мероприятий найдите наибольшее количество мероприятий, которые можно провести в одном зале, и время окончания последнего из них».
3. «Покупатель берёт товары по порядку цены; найдите сумму скидки при заданных правилах».
4. «Зрители выбирают места; найдите ряд с наибольшим числом подряд свободных мест» — здесь сортировка по ряду и месту, а потом проход по соседним элементам.

Пошаговый метод

1. Прочитайте файл и проверьте, что количество записей совпадает с указанным в первой строке.
2. Поймите, какой выбор жадный. Чтобы взять как можно больше предметов при ограничении на сумму, выгодно брать самые лёгкие. Чтобы провести как можно больше мероприятий, выгодно брать то, которое раньше всех заканчивается.
3. Отсортируйте по выбранному ключу и пройдите по списку, добавляя элементы, пока это допустимо.
4. Ответьте на вторую часть. Например, чтобы максимизировать самый тяжёлый предмет при том же количестве, оставьте k − 1 самых лёгких предметов и замените последний на самый тяжёлый, который ещё помещается.
5. Проверьте на маленьком наборе полным перебором — так вы убедитесь, что жадная идея верна.

Разбор примера 1 (загрузка с ограничением)

Грузоподъёмность фургона — 100 кг. Есть 11 коробок массой (кг): 23, 7, 41, 15, 30, 12, 9, 26, 18, 35, 11. Найдите наибольшее количество коробок, которые можно погрузить, и наибольшую возможную массу самой тяжёлой коробки среди всех наборов с таким количеством.

Шаг 1. Сортируем: 7, 9, 11, 12, 15, 18, 23, 26, 30, 35, 41.

Шаг 2. Берём самые лёгкие. Суммы: 7, 16, 27, 39, 54, 72, 95. Следующая коробка (26) даст 121 > 100. Значит, можно взять 7 коробок, и больше нельзя: любые 8 коробок весят не меньше восьми самых лёгких, то есть 121.

Шаг 3. Максимизируем самую тяжёлую. Оставляем 6 самых лёгких (сумма 72), свободно ещё 100 − 72 = 28 кг. Самая тяжёлая из оставшихся коробок, которая помещается в 28 кг, — 26 кг. Набор 7, 9, 11, 12, 15, 18, 26 весит 98 кг.

Ответ: 7 26.

Почему оставляем именно 6 самых лёгких: если в наборе есть более тяжёлые коробки, свободное место для самой тяжёлой только уменьшается.

Разбор примера 2 (заявки на зал)

Поступили заявки на проведение мероприятий в одном зале, для каждого указано время начала и окончания (в часах): (2, 5), (1, 3), (4, 8), (6, 7), (3, 6), (7, 10), (9, 12), (8, 9), (11, 14), (10, 13). Мероприятие может начаться в момент окончания предыдущего. Какое наибольшее количество мероприятий можно провести?

Сортируем по времени окончания и берём каждое мероприятие, которое начинается не раньше окончания последнего выбранного: (1, 3), затем (3, 6), затем (6, 7), затем (8, 9), затем (9, 12). Остальные пересекаются с уже выбранными.

Ответ: 5. Жадный выбор «раньше всех заканчивается» оставляет максимум времени для следующих мероприятий; это классический результат, его легко проверить перебором на маленьких данных.

Код на Python

Пример 1. Формат файла: в первой строке вместимость и количество коробок, далее по одной массе в строке.

f = open('26.txt')
S, n = map(int, f.readline().split())
a = sorted(int(f.readline()) for _ in range(n))

k, total = 0, 0
while k < n and total + a[k] <= S:
    total += a[k]
    k += 1

rest = S - sum(a[:k - 1])                    # место для самой тяжёлой
heaviest = max(x for x in a[k - 1:] if x <= rest)
print(k, heaviest)                           # 7 26 для данных примера

Пример 2. Заявки — пары чисел «начало окончание».

req = [tuple(map(int, line.split())) for line in open('26.txt')]

count, last = 0, -1
for s, e in sorted(req, key=lambda r: r[1]):
    if s >= last:
        count += 1
        last = e
print(count, last)                           # 5 12 для данных примера

Обе программы работают за время сортировки, поэтому файл даже из миллиона строк обрабатывается за секунды.

Как убедиться, что жадность работает

Для маленького набора данных (до 15–20 элементов) можно перебрать все подмножества с помощью itertools.combinations и сравнить результат с жадным алгоритмом. Если ответы совпали на нескольких случайных наборах, идея скорее всего верна. Полезно и рассуждение «от противного»: предположим, что в лучшем наборе есть коробка тяжелее, чем одна из невыбранных; заменим её на более лёгкую — сумма уменьшится, а количество не изменится. Значит, всегда существует оптимальный набор из самых лёгких коробок. Такое рассуждение называется аргументом замены и подходит для большинства задач этого типа.

Частые ошибки

• Сортируют по началу, а не по окончанию в задаче о заявках: такой выбор не оптимален.
• Неправильно отвечают на вторую часть: просто берут k-й элемент отсортированного списка. Нужно освободить место и найти самый большой подходящий элемент среди оставшихся.
• Путают строгие и нестрогие неравенства. «Может начаться в момент окончания» — это s >= last; «должно быть хотя бы 1 час перерыва» — уже другое условие.
• Не учитывают повторяющиеся значения. Одинаковые массы — разные коробки; не используйте множества вместо списков.
• Читают первую строку как данные. Параметры задачи в первой строке нужно отделить.
• Применяют жадность там, где она не работает. Если нужно набрать максимальную сумму, не превышающую S, жадный выбор ошибается — это уже задача о рюкзаке.

Потренируйтесь

Решите задания № 26 в банке и задачи с проверкой кода, где программа проверяется на больших входных данных. Следующее и последнее задание экзамена — задание 27: кластеризация данных.