Štapovi
Imamo N štapova. Spajanje dvaju štapova duljina a i b daje štap duljine a + b i košta a + b. Kolika je najmanja cijena spajanja svih štapova u jedan?
- Ulaz
U prvom retku N. U drugom retku N duljina.
- Izlaz
Najmanja cijena.
- Ograničenja
1 ≤ N ≤ 100 000, 1 ≤ duljina ≤ 10⁹
Primjer 1
Ulaz
4 4 3 2 6
Izlaz
29
Zapeo si?
Prvo pokušaj sam. Savjeti se otvaraju jedan po jedan, svaki otkriva malo više.
Pohlepno: koja dva štapa je najbolje spojiti?
Novi štap ide natrag među ostale.