Задание 26 ЕГЭ по информатике · EDE407
Мероприятия в конференц-залеВысокаяКЭС 3.10
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
В первой строке входного файла находится натуральное число N (N≤1000) — количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Для выполнения задания используйте данные из прилагаемого файла.
1_EDE407.zipВ первой строке входного файла находится натуральное число N (N≤1000) — количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Для выполнения задания используйте данные из прилагаемого файла.
Показать ответ
23 19
Подсказки (3)
- Какие два мероприятия можно проводить последовательно? Учитывайте, что окончание первого может совпадать с началом второго.
- Отсортируйте заявки по времени окончания и для каждой заявки найдите максимальное число мероприятий, которые могут завершаться этим мероприятием.
- Для каждой пары совместимых мероприятий j и i, где endj≤starti, рассмотрите переход dpi=dpj+1. При переходе запоминайте перерыв starti−endj как возможный перерыв между двумя последними мероприятиями.
Решение
1. Для каждой заявки обозначим время начала через starti, а время окончания — через endi. Две заявки j и i совместимы, если мероприятие j заканчивается не позднее начала мероприятия i.
endj≤starti
2. Отсортируем все заявки по времени окончания. Для каждой заявки i вычислим dpi — максимальное количество мероприятий в расписании, последним из которых является мероприятие i.
3. Переберём все пары заявок. Если endj≤starti, то можно добавить мероприятие i после расписания, заканчивающегося мероприятием j.
dpi=max(dpi,dpj+1)
4. Если переход образует расписание с максимальным количеством мероприятий, вычислим перерыв между двумя последними мероприятиями.
gap=starti−endj
5. Среди всех расписаний с максимальной длиной выберем максимальное значение gap.
endj≤starti
2. Отсортируем все заявки по времени окончания. Для каждой заявки i вычислим dpi — максимальное количество мероприятий в расписании, последним из которых является мероприятие i.
3. Переберём все пары заявок. Если endj≤starti, то можно добавить мероприятие i после расписания, заканчивающегося мероприятием j.
dpi=max(dpi,dpj+1)
4. Если переход образует расписание с максимальным количеством мероприятий, вычислим перерыв между двумя последними мероприятиями.
gap=starti−endj
5. Среди всех расписаний с максимальной длиной выберем максимальное значение gap.
Частые ошибки
- Считать мероприятия несовместимыми при совпадении времени окончания одного и начала другого.
- Максимизировать только число мероприятий и не сравнивать перерывы между последними мероприятиями.
- Вычислять перерыв как разность времён начала вместо разности начала следующего и окончания предыдущего мероприятия.
- Использовать только жадный выбор самого раннего окончания без дополнительного учёта максимального перерыва.
Источник: Открытый банк ФИПИ
Похожие задания
26Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · A9339F26Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · B1238C26Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · B4222426Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · E53C3B26Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 02861826В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно…Коробки и коржи: вложение с заданной разностью · 05BFA6
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.