noip普及講座8-堆及其應用-資料下載頁
2025-11-08 05:39本頁面
【正文】 問題了。 (2) 算法: a.從森林里取兩個權和最小的結點； b.將它們的權和相加，得到新的結點，并且把原結點刪除，將新結點插入到森林中； c.重復(a)～(b)，直到整個森林里只有一棵樹。,第三十二頁，共三十九頁。,堆的應用,【算法實現(xiàn)】 該問題是貪心算法，可用堆的兩個基本操作來實現(xiàn)：首先，建立小根堆，并不斷重復如下操作：分別讀取兩個最小數(shù)累加起來，并且形成一個新的結點，將新結點插入到堆的尾部。利用堆調整使整個數(shù)組仍然是最小堆，重復此操作，直到僅有一個結點。,第三十三頁，共三十九頁。,堆的應用,第三十四頁，共三十九頁。,堆的應用,第三十五頁，共三十九頁。,堆的應用,len:=0。 read(n)。 for i:=1 to n do begin read(tmp)。 put(tmp)。 end。 ans:=0。 for i:=1 to n1 do begin a:=get。 b:=get。 ans:=ans+a+b。 put(a+b)。 end。 writeln(ans)。,第三十六頁，共三十九頁。,堆的應用,sum=0。 cinn。 for (int i=1。ix。 put(x)。 } for (int i=1。i=n1。i++) { int a=get(),b=get()。 sum=sum+a+b。 put(a+b)。 } coutsumendl。,第三十七頁，共三十九頁。,堆的應用,【時間復雜度】 get和put操作的復雜度均為log2n。所以建堆復雜度為nlog2n。 合并果子時，每次需要從堆中取出兩個數(shù)，然后再加入一個數(shù)，因此一次合并的復雜度為3log2n，共n1次。 所以整道題目的復雜度是nlog2n。,第三十八頁，共三十九頁。,內容總結,堆及其應用。樹中每個結點與數(shù)組中存放該結點中值的那個元素相對應。var fa,son,tmp:longint。len:=len+1。int fa,son,tmp。son=son/2。var pa,son,tmp:longint。len:=len1。?其中的關鍵操作：取最小結點、插入新結點。i:=i+1。cinn。(pas,c,c++)。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。ans:=ans+a+b,第三十九頁，共三十九
物理相關推薦
鄂ICP備17016276號-1