Editorial for Skladiste


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

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 n kutija koje će biti izvađene u trenucima T_0, T_1, \dots, T_n, i neka je vreme vađenja one koju trenutno ubacujemo t.

Ako je ukupno vreme potrebno da se izvade kutije koje su trenutno u skladištu R (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 T_i > t, tako da je ukupno vreme R + |i : T_i > t|.
  • novu kutiju stavimo na početak: za kutije koje se vade pre nje (T_i < t), vreme će se povećati za 1, a za novu kutiju će vreme vađenja biti 0. Novo ukupno vreme je dakle R + |i : T_i < t|.

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 \mathcal{O}(N \log{N}), neophodna nam je struktura koja podržava sledeće operacije u logaritamskom vremenu:

  • dodaj x u skup,
  • izbaci x iz skupa, i
  • odgovori na "koliko elemenata skupa su manji od x?"

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 2N), jedna alternativa je segmentno stablo (ili Fenwick stablo). Ovde, u i-tom elementu čuvamo 1 ako je i u skupu, i 0 u suprotnom. Upit se u tom slučaju svodi na pronalaženje zbira na intervalu [0, x).


Comments

There are no comments at the moment.