Зал брони

Пусть мы выбрали точку в которой будет располагаться люк. Тогда если увеличить эту координату на единицу, сумма расстояний до нее от всех костюмов увеличится на число костюмов, которые находятся в меньших координатах и уменьшится на количество костюмов, которые до увеличения находились в больших координатах.

Отсюда получим, что если можно поставить люк между какими-то двумя отсеками, можно поставить в каком-то из них, и ответ не ухудшится.

Тогда переберем все точки, в которых находится хотя бы один отсек, поддерживая сколько костюмов находятся до и после текущей координаты. И таким образом найдем оптимальную точку.

Замечание: Из выше описанных рассуждений можно заметить, что оптимальный ответ всегда будет достигаться в первой координате, такой что сумма костюмов в ней и предыдущих точках больше либо равна половине всех костюмов.