Алгоритм с использованием префексных сумм.
Попробуем сформулировать задачу в более простом общем виде.
Будем считать, что антенны расположены на каждом км и передают неотрицательное число пакетов.
Пусть W=[w
1, w
2,...,w
n], w
i - количество пакетов, которое передается с i-го км.
Рассмотрим расположение "Центра обработки" (ЦО) в точке с номером j (то есть на j-м км)
и определим SLj, SRj (веса слева и справа), положив:
- \(SL_j=w_1\cdot|j-1|+\cdots+w_{j-1}\cdot|j-(j-1)|\) - сумма энергии (моментов масс) элементов "слева" от перекладины;
- \(SR_j=w_{j+1}\cdot|(j+1)-j|+\cdots+w_{j-1}\cdot|n-j|\) - сумма энергии (моментов масс) элементов "справа" от перекладины;
Также определим S, Sj- и Sj+, положив:
- \(S=w_1+\cdots+w_{n} \) - сумма всех элементов
- \(S_{j-}=w_1+\cdots+w_{j-1} \) - префиксная сумма элементов "до j"
- \(S_{j+}=w_{j}+w_{j+1}+\cdots+w_{n} \) - префиксная сумма элементов "от j"
Нетрудно заметить, что:
- \(S_{j+}=S-S_{j-}\)
- \(SL_{i}=SL_{i-1}+S_{i-}\)
- \(SR_{i}=SR_{i-1}-S_{i+}=SR_{i-1}-S+S_{i-} \)
Нам необходимо миминизировать значение SL
i+SR
i, для которого получаем, что:
Таким образом, получаем, что:
\(F[i]=SL_{i}+SR_{i}=SL_{i-1}+SRL_{i-1}+2\cdot S_{i-}-S=F[i-1]+d_i , \ где\ d_i=2\cdot S_{i-}-S \)
Мы уже знаем, что F[i] - выпуклая фунция, поэтому надо найти такое i, что:
- \(d_{i-1} < 0\ и\ d_i\geq0 \)
Это можно сделать за
O(n) с помощью следующего алгоритма:
- Считать данные и "построить" массив префексных сумм PS, где PS[-1] - cумма всех элементов
- Найти j, такое что : \(2\cdot PS[j-1]<PS[-1],\ а\ 2\cdot PS[j]\geq PS[-1]\)
(поиск j можно вести "в линию", а можно бинарным поиском (PS - неубывающий массив)