Наивно решење би подразумевало да се израчуна дужина каблова за сваку могућу позицију рутера и да се одабере најмањи. Да бисмо израчунали дужину каблова, ако је рутер у згради на позицији \(k\), рачунамо заправо збир
\[\sum_{i=0}^{n-1} |k-i|\cdot a_i,\]
где је \(a_i\) број корисника у згради \(i\).
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
long long minDuzinaKablova(const vector<int>& broj_stanara) {
// broj zgrada
int n = broj_stanara.size();
// minimalna duzina kablova
long long min_duzina_kablova = numeric_limits<long long>::max();
// obrađujemo sve zgrade od 0 do n-1
for (int k = 0; k < n; k++) {
// duzina kablova ako je ruter u zgradi broj k
long long duzina_kablova = 0;
for (int i = 0; i < k; i++)
duzina_kablova += (k - i) * broj_stanara[i];
for (int i = k+1; i < n; i++)
duzina_kablova += (i - k) * broj_stanara[i];
if (duzina_kablova < min_duzina_kablova)
min_duzina_kablova = duzina_kablova;
}
return min_duzina_kablova;
}
int main() {
int n;
cin >> n;
vector<int> broj_stanara(n);
for (int i = 0; i < n; i++)
cin >> broj_stanara[i];
cout << minDuzinaKablova(broj_stanara) << endl;
return 0;
}Сложеност. Сваки тежински збир можемо израчунати у времену \(O(n)\), па пошто се испитује \(n\) позиција, алгоритам је сложености \(O(n^2)\).
Много боље решење и линеарни алгоритам можемо добити ако применимо принцип инкременталности и избегнемо рачунање у сваком кораку из почетка. Размотримо како се дужина каблова мења када се рутер помера са зграде \(k\) на зграду \(k+1\).
Дужину каблова за рутер у згради \(k+1\) добијамо од дужине каблова за рутер у згради \(k\) тако што ту дужину увећамо за укупан број станара закључно са зградом \(k\) и умањимо је за укупан број станара почевши од зграде \(k+1\). То је заправо интуитивно прилично јасно и без компликованог математичког извођења. Померањем рутера за дужину једне зграде надесно, сваком станару који живи закључно до зграде \(k\) дужина кабла се повећала за једно растојање између зграда, а свим станарима од зграде \(k+1\) надесно се та дужина смањује за једно растојање између зграда.
Доказ коректности. Формално, математички, то се може показати на следећи начин. Ако је рутер на позицији \(k\), тада је дужина каблова једнака
\[d_k = \sum_{i=0}^{k-1} (k-i)\cdot a_i + \sum_{i=k+1}^{n-1} (i-k)\cdot a_i.\]
Ако је рутер на позицији \(k+1\), тада је дужина каблова једнака
\[d_{k+1} = \sum_{i=0}^{k} (k+1-i)\cdot a_i + \sum_{i=k+2}^{n-1} (i-k-1)\cdot a_i.\]
Разлика између те две суме једнака је
\[\begin{align*} d_{k+1} - d_k &= \left(\sum_{i=0}^{k} (k+1-i) \cdot a_i - \sum_{i=0}^{k-1} (k-i)\cdot a_i\right) + \left(\sum_{i=k+2}^{n-1} (i-k-1)\cdot a_i - \sum_{i=k+1}^{n-1} (i - k) \cdot a_i\right)\\ &= \left(\sum_{i=0}^{k-1} ((k+1-i) - (k-i)) \cdot a_i\right) + a_k - a_{k+1} + \left(\sum_{i=k+2}^{n-1}((i-k-1) - (i-k)) \cdot a_i\right)\\ &= \sum_{i=0}^{k-1}a_i + a_k - a_{k-1} - \sum_{i=k+2}^{n-1} a_i\\ &= \sum_{i=0}^ka_i - \sum_{i=k+1}^{n-1}a_i \end{align*}\]
Укупне бројеве станара пре и после дате зграде можемо такође рачунати инкрементално (при преласку на наредну зграду, први број се увећава, а други умањује за број станара текуће зграде).
Дакле, у програму можемо да памтимо три ствари: дужину каблова \(d_k\) ако је рутер на позицији \(k\), укупан број станара \(pre_k\) пре зграде \(k\) (не укључујући њу) и укупан број станара \(posle_k\) од зграде \(k\) (укључујући њу) до краја. На почетку, када је \(k=0\), први број \(d_0\) морамо експлицитно израчунати као \(\sum_{i=1}^{n-1}i \cdot a_i\), други број треба иницијализовати на нулу \(pre_0 = 0\), а трећи на укупан број свих станара \(posle_k = \sum_{i=0}^{n-1}a_i\). Затим за свако \(k\) од \(1\) до \(n-1\) рачунамо \(pre_k = pre_{k-1} + a_{k-1}\), \(posle_k = posle_{k-1} - a_{k-1}\) и затим \(d_k = d_{k-1} + pre_k - posle_k\).
Пример. Илуструјмо извршавање овог алгоритма на примеру зграда у којима живи редом \(3, 5, 1, 6, 2, 4\) станара.
k dk pre_k posle_k 0 53 0 21 1 38 3 18 2 33 8 13 3 30 9 12 4 39 15 6 5 52 17 4
Приметимо да је могуће извршити и малу оптимизацију (додуше која неће поправити асимптотску сложеност) на основу монотоности низа \(d_k\) и петљу прекинути чим се број \(d_k\) први пут повећа. Наиме, вредности у том низу ће опадати до тражене минималне вредности, након чега ће кренути да расту. У претходном примеру, могли смо закључити да је минимална дужина каблова 30, чим се у наредном кораку та вредност повећала на 39.
#include <iostream>
#include <vector>
using namespace std;
long long minDuzinaKablova(const vector<int>& broj_stanara) {
// broj zgrada
int n = broj_stanara.size();
// krećemo od zgrade 0
// ukupna dužina kablova ako je ruter u tekućoj zgradi
long long duzina_kablova = 0;
for (int i = 0; i < n; i++)
duzina_kablova += broj_stanara[i] * i;
// broj stanara pre tekuće zgrade
long long stanara_pre = 0;
// broj stanara od tekuće zgrade do kraja
long long stanara_posle = 0;
for (int i = 0; i < n; i++)
stanara_posle += broj_stanara[i];
// minimalna duzina kablova
long long min_duzina_kablova = duzina_kablova;
// obrađujemo sve zgrade od 1 do n-1
for (int k = 1; k < n; k++) {
// ažuriramo brojeve stanara
stanara_pre += broj_stanara[k-1];
stanara_posle -= broj_stanara[k-1];
// ažuriramo duz
duzina_kablova += stanara_pre - stanara_posle;
if (duzina_kablova < min_duzina_kablova)
min_duzina_kablova = duzina_kablova;
}
return min_duzina_kablova;
}
int main() {
int n;
cin >> n;
vector<int> broj_stanara(n);
for (int i = 0; i < n; i++)
cin >> broj_stanara[i];
cout << minDuzinaKablova(broj_stanara) << endl;
return 0;
}Сложеност. Пошто је и за једну и за другу фазу потребно време \(O(n)\), то је уједно сложеност овог алгоритма.
Интересантно, укупну почетну дужину каблова можемо израчунати ефикасно и без множења, тако што на збир додамо број станара у последњој згради, затим број станара у последње две зграде, затим број станара у последње три зграде и тако даље, све док не додамо број станара у свим зградама осим прве.