← Natrag na lekciju 32 · Hrpa (heapq): uvijek najmanji

Štapovi

Lekcija 32 · Python vrijeme: 1,0 s memorija: 256 MB

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.

Rješenje

Za predaju rješenja se prijavi.