mPitao sam ranije u vezi sa ovim zadatkom i niko ne odgovara. Da li mogu da dobijem objasnjenje kako se radi ovaj zadatak. Dakle, znam onu ideju koja radi u O(n^2) i sad znam da to treba da se ubrza tako sto se koristi heap ali kako treba da smestamo spratove u heap?
aj pozdrav
Pa evo ti detaljnije..
Izdrzljivost jedog sprata mozes da poredis jedino sa ukupnom vodom iznad njega.
Znaci u heap smestas razliku izmedju izdrzljivosti i ukupne vode iznad sprata ( ukljucujuci i vodu na tom spratu ) i naravno sprat koji je u pitanju..
E sad, iz heap-a brises vrednosti ako je Izdrzljivost "top" sprata manja od vode koja je trenutno iznad tog sprata.Znaci voda do sprata na kome se trenutno nalazis - voda do sprata koji je na vrhu heap-a...
I tako prodjes za sve spratove, belezis minimum i naravno vodis racuna o tome kada se koji sprat rusi, tj. kad rusis neki sprat J onda stavljas R[J]=true, a kad ga brises iz heap-a menjas R[Heap.topElem] = false..
Jel jasno?
Ovako, neka je heap niz slogova sa dva registra "info" i "index".
E sad ako je heap[i].idex=j
sta je onda heap[i].info? (napisi ga kao kod da pises kod, tipa :
heap[i].info=izdrzljivost[j]-vodaNaSpratu[j] da bih te lakse razumeo)
Ovo sto si ti reko da cuvam u heap meni nikako ne ulazi u glavu a probao sam i ili nije tacno ili imam gresku u kodu
heap[i].info = Snaga[ heap[i].info ] - (UkupnaVoda - vodaDoSprata[ heap[i].info-1])
Probao sam ovako, i verovatno imam gresku u kodu koju ne primecujem...
u svakom slucaju, hvala!!
nema na cemu..
Nego, zaboravio sam jos jednu stvar.Longint ti nije dovoljan.
Znaci uzmi dougle ili int64.To bi mogla biti jedna greska.
Ne mogu da verujem da je u tipu bio problem, a pise da zbir onih cuda nece prelaziti 2^32.
Pa dobro, puno hvala!
