Минимизировать стоимость трубопровода подбором координаты

Question

Задача о строительстве газового трубопровода

Дана последовательность расстояний расположения домов от шоссе. Нужно рассчитать расположение газового трубопровода, чтобы стоимость подключения всех домов была минимальна. Все дома находятся по одну сторону от шоссе. Возможен случай, когда расстояние от дома до шоссе равно 0.

Газовый трубопровод будет строиться параллельно шоссе

func calculateLocation(houses []uint) float

Что хочется увидеть:

Алгоритм со сложностью O(N) по времени

Answer 1

Если надо подобрать x чтобы минимизировать

abs(x-a[0]) + abs(x-a[1]) + ... + abs(x-a[n-1])

Как это сделать за O(n) я не знаю, но могу за O(n*lb(n)):

Сортируем массив a и считаем его сумму r
Представим трубу в позиции p=0. Цена слева от трубы будет l=0, а справа r
Пройдём по массиву, текущий элемент x имеет индекс i, pзначение предыдущего p
```
l += i * (x-p)
r -= (n-i) * (x-p)
```
Выбираем максимум среди всех пройденных сумм l+r

https://ideone.com/esdLjV

a = [1, 2, 3, 94]

a.sort()
n = len(a)

l = 0
p = 0
r = sum(a)

res = r
pos = 0

for i,x in enumerate(a):
  l += i * (x-p)
  r -= (n-i) * (x-p)
  cur = l + r
  p = x
  
  if cur < res:
    res = cur
    pos = x
  
print(pos, res)

PS: Почему достаточно посматривать только точки с домами, можно подумать самостоятельно.

БЛОГ НА HUSL

Минимизировать стоимость трубопровода подбором координаты

Ответы (1 шт):