← Natrag na lekciju 28 · Pohlepni algoritmi (greedy)

Red u knjižnici

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

U knjižnici čeka N učenika. Za svakog znamo koliko minuta traje njegovo posuđivanje. Učenik čeka dok se ne posluže svi ispred njega. Kojim redoslijedom treba posluživati da ukupno čekanje svih učenika bude najmanje? Ispiši to najmanje ukupno čekanje.

Ulaz

U prvom retku N. U drugom retku N trajanja u minutama.

Izlaz

Najmanje ukupno čekanje.

Ograničenja

1 ≤ N ≤ 100 000, trajanja od 1 do 1000

Primjer 1

Ulaz
3
5 1 3
Izlaz
5

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.