Editorial for Skladiste
Submitting an official solution before solving the problem yourself is a bannable offence.
Posmatrajmo trenutak dostave jedne od kutija. Neka se u skladištu trenutno nalazi kutija koje će biti izvađene u trenucima
, i neka je vreme vađenja one koju trenutno ubacujemo
.
Ako je ukupno vreme potrebno da se izvade kutije koje su trenutno u skladištu (ako nema daljih dostava), nakon što dodamo novu, postoje dve mogućnosti:
- novu kutiju stavimo na kraj: vremena vađenja pojedinačnih kutija koje su već u skladištu se neće promeniti. Kada nova kutija dođe na red, ispred nje će biti one za koje važi
, tako da je ukupno vreme
.
- novu kutiju stavimo na početak: za kutije koje se vade pre nje (
), vreme će se povećati za
, a za novu kutiju će vreme vađenja biti
. Novo ukupno vreme je dakle
.
Primetimo da ove dve vrednosti uopšte ne zavise od trenutnog redosleda kutija u skladištu. Samim tim, izbor koji daje manje ukupno vreme je optimalan i u slučaju u kom trenutna kutija nije poslednja, tako da je dovoljno da izračunamo ove dve vrednosti za svaku kutiju i odaberemo manju.
Da bi dobili rešenje čija je vremenska složenost , neophodna nam je struktura koja podržava sledeće operacije u logaritamskom vremenu:
- dodaj
u skup,
- izbaci
iz skupa, i
- odgovori na "koliko elemenata skupa su manji od
?"
Jedna opcija je struktura slična set-u, ali C++ standardna biblioteka ne podržava direktno upit koji nam je potreban. Pošto su svi elementi mali (maksimalno ), jedna alternativa je segmentno stablo (ili Fenwick stablo). Ovde, u
-tom elementu čuvamo
ako je
u skupu, i
u suprotnom. Upit se u tom slučaju svodi na pronalaženje zbira na intervalu
.
Comments