Решение задачи День рождения с Codeforces
Без пояснения   Просмотров: 149
У ковбоя Влада день рождения! На праздник собрались n детей. Чтобы поздравить Влада, дети решили водить вокруг него хоровод. Среди детей, пришедших к Владу, есть и высокие, и низкие, поэтому если они встанут в хороводе как угодно, то рядом могут оказаться очень высокий и очень низкий ребёнок, и им будет трудно держаться за руки. Поэтому дети хотят встать в хоровод так, чтобы максимальная разность ростов двух соседних детей была бы минимальной возможной.
Формально, пронумеруем детей от 1 до n по кругу, то есть для каждого i ребёнок с номером i является соседним с рёбенком с номером i+1, а также ребёнок с номером 1, является соседом с ребёнок с номером n. Тогда неудобством этого хоровода назовём максимальный модуль разности ростов детей, которые стоят рядом.
Помогите детям определить в каком порядке им надо перестроиться, чтобы минимизировать неудобство получившегося хоровода.
Формально, пронумеруем детей от 1 до n по кругу, то есть для каждого i ребёнок с номером i является соседним с рёбенком с номером i+1, а также ребёнок с номером 1, является соседом с ребёнок с номером n. Тогда неудобством этого хоровода назовём максимальный модуль разности ростов детей, которые стоят рядом.
Помогите детям определить в каком порядке им надо перестроиться, чтобы минимизировать неудобство получившегося хоровода.