題目出處:APCS202506
zerojudge連結:https://zerojudge.tw/ShowProblem?problemid=q838
解題策略:本題可以使用線段樹,如果不會,可以使用priority_queue與Double LinkedList。
priority_queue用於取出最小值與編號,Double LinkedList用於將最小值加到下一個元素,因為priority_queue要修改某個元素的數值,效率差且不好寫,只先修改Double LinkedList內下一個元素的數值,從priority_queue取出最小值與編號,並刪除該元素。
先確認是否搬得動,接著判斷是否該編號在Double LinkedList內的元素數值是否有修改過,如果沒有修改過,則將該元素的數值累加到總分,將該元素的數值累加到Double LinkedList內下一個元素,修改Double LinkedList刪除該元素;否則有修改過,從Double LinkedList取得該元素的新數值,使用新數值與編號建立新元素加入priority_queue。
參考程式碼
以下使用線段樹解題
本題可以使用線段樹,計算區間的最小值與最小值索引值。動態更新線段樹的葉節點數值,並由下到上更新最小值與最小值索引值。使用DoubleLinkedList找出最小值的下一個元素,將數值累加到下一個數值,並由下到上更新最小值與最小值索引值。
線段樹參考程式碼