【DSA】作業四,News Headline Generator

這個作業主要是實作heap tree,加上一堆麻煩的小陷阱

主要是給你一個pair<id,score>,依據score來排序,有三個動作:insert,update,print

insert就是把pair放進樹裡,update是幫特定id增加額外的score,print是印出score最高的pair

看到題目的當下我就覺得自己刻一個用vector來實現的Max Heap Tree Class,主要幾個member function就是insert,upheap,swapNode,update跟printRoot,member data就一個vector<pair<id,score>>存資料,vector<int>當作iterator來操作樹存放vector<pair<id,score>>的index,一個unordered_map<id,index>來記錄id對應的位置,這樣update的時候只要O(1),直接找出id對應的位置加上額外的score

大致的架構很快就完成了,一個晚上吧(老實說我寫code很喜歡東摸西摸,真正花時間寫也只有兩三個小時),唯一麻煩的是我額外用iterator有點繞有點小麻煩哈哈,但馬上遇到了陷阱:每次insert一個新的pair進去時,已存在樹裡面的每個pair的score會減掉特定數字,如果我每次insert都減,跑一百萬筆資料下來,會超過時間限制(2秒)

解決辦法是,觀察每次每個pair要減去多少次特定數字的相對關係,第一個會減掉(insert次數*特定數字),第二個(insert次數-1*特定數字),這樣代表第一個insert的跟第二個insert的會差一個特定數字,第n個跟第一個匯差n-1個特定數字,那我一開始在score就加上(insert次數*特定數字),這樣下來,他們彼此的差距就不會變,最後要輸出時再減掉目前的insert次數,搞定!(只是要注意overflow,為此我幾乎把所有變數宣告成long long)

這個作業算是第一次自己動手刻樹(幾乎沒參考網路上的,自己刻,想法幾乎都自己想到的),速度也不錯,不過前面還是有一堆怪物,只好放個剛交出來排名不錯的時候的照片哈哈(現在已跌出排行榜)

(放在Github上的code)