Каталог: Задание №26. Жадные алгоритмы, сортировка и оптимизация

Банк задач: 198 Формат ЕГЭ 2026 Высокий (2 балла) 10-15 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №26

Тема кодификатора Конференц-залы (интервалы времени), камеры хранения / парковки с ячейками, кинотеатры (ряды и места), упаковка грузов

Сложность и баллы Высокий (2 балла)

Рекомендуемое время 10-15 мин

Инструменты решения Python 3, open('26.txt'), sort(key=lambda ...), defaultdict(list), Массив ячеек [0]*K

Одно из двух самых ценных заданий ЕГЭ (2 первичных балла!). Требует применения правильной стратегии сортировки и жадного выбора: отрезки мероприятий, распределение клиентов по ячейкам камеры хранения, анализ мест в зале или оптимизация загрузки.

Основные прототипы и разновидности

Тип 1: Мероприятия в конференц-зале (выбор по времени окончания)

Сортировка по правому концу events.sort(key=lambda x: x[1]). Максимальное количество непересекающихся отрезков.

Тип 2: Камеры хранения / Парковка с K ячейками (Хит 2024-2026)

Клиенты занимают свободную ячейку с наименьшим номером. Массив cells = [0] * (K + 1) для времени освобождения.

Тип 3: Места в кинотеатре (defaultdict по рядам)

Группировка занятых мест по рядам и поиск двух соседних мест с разницей ровно K (например, c2 - c1 == 3).

Тип 4: Загрузка файлов на диск / Упаковка контейнеров

Жадный рюкзак: сортировка по возрастанию и замена последнего выбранного элемента на максимально возможный.

Теоретический фундамент и алгоритмы

1. Теорема об отрезках (Конференц-зал):

Чтобы выбрать максимальное количество непересекающихся мероприятий:

Сортируем все мероприятия СТРОГО по времени их окончания: events.sort(key=lambda x: x[1]).
Берем первое мероприятие selected = [events[0]].
Для каждого следующего проверяем: если start >= selected[-1][1], добавляем его.
Для поиска максимально позднего времени окончания: берем время предпоследнего мероприятия last_start = selected[-2][1] и ищем максимум end среди всех мероприятий с start >= last_start.

2. Алгоритм для K камер хранения / парковок (Хит последних лет):

with open('26.txt') as f:
    lines = f.readlines()
    K = int(lines[0])
    N = int(lines[1])
    passengers = [list(map(int, line.split())) for line in lines[2:] if line.strip()]

# Сортируем пассажиров по времени прибытия:
passengers.sort(key=lambda x: x[0])

cells = [0] * (K + 1) # Время освобождения каждой ячейки (1..K)
served_count = 0
last_cell = 0

for start, end in passengers:
    # Ищем свободную ячейку с НАИМЕНЬШИМ номером:
    for c in range(1, K + 1):
        if cells[c] < start:
            cells[c] = end
            served_count += 1
            last_cell = c
            break

print("Обслужено пассажиров:", served_count, "Номер последней ячейки:", last_cell)

Лайфхаки и фишки для ускорения

Совет

При сортировке кортежей по нескольким полям используйте sort(key=lambda x: (x[0], -x[1])).

Совет

Для группировки используйте from collections import defaultdict; d = defaultdict(list).

Частые ошибки и экзаменационные ловушки

Ошибка: Сортировать мероприятия по времени начала x[0]
Жадный выбор по началу отрезка НЕ дает оптимального количества мероприятий!

Правильно: Для конференц-зала ВСЕГДА сортировать по времени окончания: x[1].

Ошибка: Забыть прибавить 1 к размеру массива ячеек: cells = [0] * K
Ячейки нумеруются с 1, поэтому размер должен быть K + 1!

Правильно: Создавать массив cells = [0] * (K + 1) и итерироваться for c in range(1, K + 1).

ГРОБ №26: Камеры хранения с временем выгрузки багажа (+ 1 минута)

Ячейка освобождается только через 1 минуту после того, как клиент забрал вещи.

Алгоритм решения: Учитывайте время освобождения как `cells[c] = end + 1` или `cells[c] <= start` в зависимости от строгости условия.

Практические задачи из банка КИМ (Всего: 198)

Решать в песочнице СмартКИМ

Задача #9009 №26 ЕГЭ