Задание 26: сортировка и жадный выбор
Коротко
В задании 26 из файла читают данные (размеры файлов, время заявок, ряды и места), сортируют и применяют жадный алгоритм. Классика: чтобы поместить на диск как можно больше файлов, берут самые маленькие. Затем, чтобы определить максимальный размер файла в таком наборе, заменяют самый большой из взятых на наибольший, который ещё помещается. Ответ — два числа.
Классическая задача
- Отсортируйте размеры по возрастанию.
- Берите файлы, пока помещаются — это максимальное количество.
- Уберите последний взятый и найдите наибольший файл, который поместится в освободившееся место.
Пример
Диск 100, файлы 10, 20, 30, 40, 50.
- 10 + 20 + 30 + 40 = 100 → 4 файла.
- Заменить 40 на 50 нельзя: 10 + 20 + 30 + 50 = 110 > 100. Максимальный файл — 40.
Другие типы
- Заявки на ресурс: сортировка по времени начала/окончания.
- Места в зале: сортировка пар (ряд, место) и поиск соседей.
Типичные ошибки
- Не сортируют данные.
- Ищут максимальный файл, нарушив максимальное количество.
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 26
Пример 1 из 2
Диск 100, файлы 10, 20, 30, 40, 50. Сколько файлов можно записать и каков наибольший размер файла в таком наборе?
- Разбор
- 10 + 20 + 30 + 40 = 100 → 4 файла; с 50 сумма 110.
- Ответ
- 4 40
Пример 2 из 2
Что сделать с данными в первую очередь?
- Разбор
- Жадный выбор требует порядка.
- Ответ
- Отсортировать
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Как взять максимум файлов?
Показать ответ
Ответ: Брать самые маленькие.
Жадный выбор.
- Вопрос 2 из 5
Что делать после сортировки?
Показать ответ
Ответ: Набирать, пока помещается.
Сумма ≤ объёма.
- Вопрос 3 из 5
Как найти наибольший файл набора?
Показать ответ
Ответ: Заменить последний взятый на наибольший возможный.
Не меняя количество.
- Вопрос 4 из 5
Метод сортировки в Python?
Показать ответ
Ответ: sort() или sorted().
По возрастанию.
- Вопрос 5 из 5
Сколько чисел в ответе обычно?
Показать ответ
Ответ: Два.
Через пробел.
Проверьте всё задание 26, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти