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