Question

Очень прошу, Вас, срочно нужно решить задачу.В Волшебной стране раз в неделю все маги работают в высотном офисном здании. Особенность офисного здания состоит в том, что в нем нельзя пользоваться волшебными палочками для перемещения по этажам, иначе дом может рухнуть. Поэтому все маги либо едут на лифте, либо идут пешком по лестнице. Сегодня у лифта на первом этаже 2020-этажного офисного здания собрались 2019 магов, которым нужно подняться вверх, причем на разные этажи. Лифт может сделать лишь один рейс на любой этаж, а дальше все должны идти пешком. Лифт способен вместить всех магов. Известно, что все маги с одинаковым неудовольствием спускаются вниз на один этаж и с двойным неудовольствием поднимаются пешком вверх на один этаж. На каком этаже нужно остановить лифт, чтобы суммарное неудовольствие было наименьшим? Если вариантов ответа несколько, укажите самый нижний из возможных этажей. Все маги должны исходно зайти в лифт. Комментарий. Если бы в здании было 4 этажа, то лифт нужно было бы остановить на третьем, в этом случае суммарное неудовольствие минимально и составляет 3 единицы (один маг с неудовольствием 2 поднимается на четвертый этаж, один маг не испытывает неудовольствия вообще, один маг с неудовольствием 1 спускается вниз на второй этаж). Заметим, что при на четвертом этаже лифт тоже можно было остановить (суммарное неудовольствие в этом случае так же составляет 3 единицы), но по условию, в качестве ответа нужно указать наименьший возможный этаж, если вариантов несколько.

Answer 1

Решение брутфорсом в одно LINQ-выраженние на скриншоте.

Answer 2

Для решения этой задачи нужно вычислить суммарное неудовольствие для каждого возможного этажа, на который может остановиться лифт, и выбрать этаж с наименьшим суммарным неудовольствием.

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

$$\sum_{i=1}^{n}(2|i-k|-1)$$

где n = 2019 - количество магов, k - номер этажа, на котором остановился лифт, |i-k| - расстояние от мага i до этажа k.

Вычисляя эту формулу для каждого возможного этажа от 1 до 2019 и выбирая этаж с наименьшим суммарным неудовольствием, мы найдем ответ на задачу.

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

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