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