Сортировка и отбор данных

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

Высокий уровеньPythonСортировка50–65 мин✓ Полный урок

Что нужно понимать

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

sort

Сортировка

Для максимизации количества объектов часто сначала берут самые маленькие.

greedy

Жадный выбор

Добавляем объект, пока не превышен общий ресурс.

swap

Второй критерий

После максимизации количества улучшаем дополнительный показатель заменой последнего элемента.

Ключевая идея

В типовой задаче сначала нужно максимизировать количество выбранных элементов, а уже среди решений с этим количеством — второй параметр. Не смешивайте эти два этапа.

Надёжный алгоритм решения

Отсортируй данные

Для задачи на максимальное число файлов — по возрастанию размера.

Набирай минимум

Добавляй самые маленькие, пока помещаются.

Зафиксируй count

Это максимально возможное количество элементов.

Освободи место последнего

Оставь первые count−1 минимальных элементов.

Найди крупнейшую замену

Выбери максимальный допустимый элемент, сохраняющий count.

Типичная ошибка: Просто взять count самых маленьких — достаточно только для первого ответа. Второй ответ часто требует заменить самый большой из выбранных на ещё больший допустимый.

Пошаговый разбор

Вместимость S=100. Размеры файлов: 10, 20, 20, 30, 35, 40.

Исходные данныеМодель

10+20+20+30 = 80
+35 → 115 > 100

Максимально можно сохранить 4 файла.

РезультатРазбор

Для второго критерия оставляем три минимальных: 10+20+20=50.

Остаётся 50, поэтому крупнейший существующий файл, который можно добавить, — 40.

РазборОткрывай шаги по очереди

Сумма четырёх минимальных 80 ≤ 100, пяти минимальных 115 > 100. Значит count=4.

Для сохранения четырёх файлов выгодно оставить 10,20,20.

Свободно 50. Из имеющихся кандидатов максимум — 40.

Тренажёр

Ответь на оба вопроса. Правильные ответы автоматически отмечают практику выполненной.

Практика

Закрепи алгоритм

2 вопроса

Каково максимальное число файлов в примере?

Каков максимальный размер одного файла при сохранении максимального количества?

Шпаргалка на экзамен

Сначала оптимизируй главный критерий.
Сортировка часто превращает задачу в жадную.
Для второго ответа проверь замену последнего выбранного элемента.
Всегда тестируй итоговую сумму на ограничение S.

Урок 26 завершён

Продолжай по маршруту

Прогресс урока сохраняется локально в браузере.

← Задание 25 Задание 27 →

Тематика «Обработка целочисленной информации» сверена с актуальным каталогом ЕГЭ‑2026; примеры и тренажёры ТурбоУроки составлены самостоятельно. Каталог заданий ↗