Задача по математике

JIeva

Подкинули тут задачу школьную, ответ вроде понятен, а вот как доказать что именно он, то туплю что-то слегка.
Есть 100 парней и 100 девушек. У каждой девушки есть список, в котором упорядочены парни в порядке предпочтений от 1го до 100го, нужно разбить их по парам. Если девушка в итоге встречается с парнем номер 1 из списка, то прибавляем 1, если с парнем номер N из своего списка, то прибавляем N. Хотим чтобы такая сумма по всем девушкам была минимальна. Чему будет равна эта сумма в наихудшем сценарии?

griz_a

А доказать просто. Начинаем с первой девушки и даем девушкам первого юношу из ее списка, который еще не занят. Соответственно, в худшем случае будет 1+2+....+100. Пример того, что такая сумма бывает, тривиальный

JIeva

точно, не с той стороны начал, пример был очевиден с самого начала
спасибо!

mtk79

даем девушкам первого юношу из ее списка, который еще не занят
с чего бы вдруг? может, альфа-самец этой девушки запал на другую?

griz_a

У юношей в этой задаче никаких списков нет, им хочется половой жизни, а с кем - неважно.
Оставить комментарий
Имя или ник:
Комментарий: