Высокий (2 балла) Время: 10-15 мин Python 3 open('26.txt') sort(key=lambda ...) defaultdict(list) Массив ячеек [0]*K Все задачи №{ topic_num } в каталоге

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

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

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

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)

Разновидности и прототипы задания на экзамене

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

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

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

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

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

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

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

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

Боевой шаблон решения на Python

Запустить код в онлайн-песочнице

# === Универсальный боевой шаблон Задания №26 на Python ===

# --- ТИП 1: Мероприятия в конференц-зале (open('26.txt')) ---
with open('26.txt') as f:
    lines = f.readlines()
    n = int(lines[0])
    events = [list(map(int, line.split())) for line in lines[1:] if line.strip()]

# Сортируем строго по окончанию (x[1]):
events.sort(key=lambda x: x[1])

selected = [events[0]]
for start, end in events[1:]:
    if start >= selected[-1][1]:
        selected.append([start, end])

print("1. Количество мероприятий:", len(selected))
last_start = selected[-2][1]
max_end = max(end for start, end in events if start >= last_start)
print("2. Макс. время окончания последнего:", max_end)

# --- ТИП 3: Места в зрительном зале (defaultdict по рядам) ---
# from collections import defaultdict
# rows = defaultdict(list)
# for r, c in points:
#     rows[r].append(c)
# 
# best_row = 0
# best_col = 0
# for r in sorted(rows.keys(), reverse=True): # Ищем максимальный ряд
#     cols = sorted(rows[r])
#     for i in range(len(cols) - 1):
#         if cols[i + 1] - cols[i] == 3: # 2 свободных места между ними
#             best_row = r
#             best_col = cols[i] + 1
#             break
#     if best_row != 0: break
# print("Ряд:", best_row, "Место:", best_col)

Анти-примеры (Типичные ошибки vs Как делать правильно)

Как делать НЕ надо:

Ошибка: Сортировать мероприятия по времени начала 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` в зависимости от строгости условия.

Лайфхаки и подводные камни на экзамене:

При сортировке кортежей по нескольким полям используйте `sort(key=lambda x: (x[0], -x[1]))`.
Для группировки используйте `from collections import defaultdict; d = defaultdict(list)`.

Банк реальных задач №26 Открыть в тренажере СмартКИМ