Выбор ответа Junior Жадные обновлено
Печенья и дети
Вопрос
У детей жадность g[i], у печений размер s[j]. Ребёнок доволен, если s[j] >= g[i]. Как накормить максимум детей?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Отсортировать оба массива и давать наименее жадному наименьшее подходящее. Наименее жадного ребёнка выгодно кормить наименьшим подходящим печеньем: крупные останутся для остальных.
Варианты ответа
- Идти по детям в исходном порядке и давать каждому самое большое печенье
- Отсортировать оба массива и давать наименее жадному наименьшее подходящееправильный ответ
- Раздавать печенья случайно, повторить много раз и выбрать лучший результат
- Динамика по подмножествам печений для каждого ребёнка, затем максимум
Разбор
Наименее жадного ребёнка выгодно кормить наименьшим подходящим печеньем: крупные останутся для остальных. O(n log n + m log m) из-за сортировок.
- Самое большое печенье нетребовательному ребёнку это трата:
g = [1, 3],s = [3, 1]даст одного довольного вместо двух. - Случайность не даёт оптимума.
- Перебор подмножеств экспоненциален.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.