UniLecs #164. Автобан
UniLecsЗадача: где-то в России строится новый автобан. Но дорога пролегает по холмистой области, и для оптимизации расходов на асфальт вам нужно сделать дорогу строго горизонтальной.
Вам необходимо выровнять поверхность под дорогу, при этом землю нельзя вывозить и завозить, а нужно распределить ее равномерно по всему участку будущего автобана. Через каждый метр от начала участка была измерена высота над уровнем моря. Напишите программу, которая по этим данным вычислит искомую высоту.
Входные данные: arr - массив, который содержит высоты участка. Высоты - натуральные числа от 1 до 10^4.
Вывод: h - высота будущего автобана.
Пример:
1. arr[4] = [0 1 1 0]
Answer = 0.66
2. arr[4] = [2 2 2 2]
Answer = 2
Идея: для простоты давайте представим задачу так: нам нужно снять слой земли до нулевого уровня, а потом равномерно "размазать" ее по всему участку автобана (см.рисунок ниже). Высоту полученного слоя нам и нужно будет найти.
Посчитаем объем земли, который был снят. Всю землю можно разделить на фигуры толщиной 1 метр, в основании которых трапеции с высотой 1 м и основаниями - двумя соседними измерениями высоты. Напомним, что площадь трапеции равна произведению полусуммы ее оснований на высоту (h).
Т.е. объем каждой фигуры V(i) = (h(i) + h(i + 1)) / 2, а полный объем:
V = V(1) + V(2) + ... + V(N - 1) =
h(1)/2 + (h(2) + h(3) + ... + h(N - 2)) + h(N - 1)/2
Первую и последную высоту мы делим пополам, остальные высоты просто суммируем. Всего таких отрезком дороги N - 1. Теперь высота "размазанного" участка земли будет равна h = V / (N - 1).
Реализация:
Source:
https://gist.github.com/unilecs/783549fec46bbdbf3e8eb23180a9c2bd
Play-test: