Равные дома
Среднее арифметическое элементов массива
По плану застройки нового района столицы Берляндии будет построено n домов, причем в i-м доме будет ai этажей.
Новому мэру столицы Берляндии план не понравился, так как он любит только дома с одинаковым количеством этажей. Вы являетесь главным архитектором Берляндии, поэтому вам было поручено изменить количество этажей в домах таким образом, чтобы каждый из n домов состоял из одинакового количества этажей. Для этого вы можете увеличивать или уменьшать количество этажей в каждом доме на произвольное число этажей. При этом в каждом доме после изменения плана должно быть целое положительное количество этажей. Если в изначальном плане дом i состоит из ai этажей, а после вашего изменения плана он будет состоять из bi этажей, то изменение i-го дома равно |ai - bi|, то есть модулю разности между ai и bi. Под суммарным изменением всех домов понимается сумма изменений каждого из n домов.
Определите минимальное суммарное изменение домов, которое нужно для того, чтобы все дома в столице Берляндии состояли из одинакового количества этажей.
Входные данные:
В первой строке следует целое число n (2 <= n <= 200000) — количество домов в столице Берляндии.
Во второй строке следует последовательность целых чисел a1, a2,..., an (1 <= ai <= 10^9), где ai равно количеству этажей в доме i согласно изначальному плану застройки.
Выходные данные
Выведите целое число — минимальное суммарное изменение домов, которое нужно для того, чтобы все дома в столице Берляндии состояли из одинакового количества этажей.
Следует обратить внимание, что ответ в этой задаче может не поместиться в стандартный 32-битный тип данных. Необходимо использовать 64-битный тип данных (long long в С++, int64 в Паскале, long в Java).
АЛГОРИТМ
- Сперва определим, сколько этажей должно быть в каждом доме. Для этого узнаем общее количество этажей во всех домах и разделим на их количество.
- Зная высоту каждого дома, не составит труда вычислить изменение для каждого дома и проссумировать все изменеия. Главное не начать в лоб раскидывать этажи по домам, задача решается чисто математически.
