主題

ZeroJudge - f607: 3. 切割費用 解題心得

Not In My Back Yard | 2021-01-24 00:00:12

題目連結:


題目大意:
第一列給定兩正整數 n 、 L (1 ≦ n ≦ 200000,1 ≦ L ≦ 10 ^ 7),代表要對一根長度為 L 單位的根子切 n 刀(每刀的位置保證不一樣)。棍子從左到右編訂位置 0 ~ L 。

接著有 n 列輸入,每列給定兩正整數 x 、 i (0 < x < L,1 ≦ i ≦ n),代表第 i 刀下刀的位置為 x 。每一次下刀的成本為被切的棍子段(可能已經切很多刀使得原本的棍子分成好幾段)之長度。

試問總成本為多少?



範例輸入:
3 7
2 2
3 1
5 3


範例輸出:
14


解題思維:
先將每一刀的正確順序重組回去(因為給定的順序不一定照下刀的順序)。

接著掃過每一刀下刀的位置,對於每個位置去找其處於的棍子段之開頭位置以及結尾位置。但是每次遍歷先前所有棍子的開頭、結尾位置並不是很理想(太慢)。

而我們可以使用平衡二元搜尋樹(Self-Balancing Binary Search Tree,如此有 AVL 樹或是紅黑樹等資料結構,例如 C++ 的 set 以及 map 即以紅黑樹實作)去儲存每個棍子段的開頭位置(一開始只有 0 ~ L 的原棍子,所以只有存 0)。

如此一來每一次搜尋的時間複雜度從全數掃過的 O(n) 變為 O(log n),所以掃過所有下刀位置並計算成本的時間複雜度為 O(n log n)。而每一刀的成本總和即是所求。



此外,以下是 C++ 使用 set 去儲存棍子開頭位置時應注意的事:
宣告一集合為 set <int> segments; 後,每次搜尋不應使用
lower_bound(segments.begin(), segments.end(), x);
去尋找位置 x (upper_bound 也同理,不應使用),應當使用
segments.lower_bound(x);

因為 C++ 的 set 資料結構不支援隨機存取(Random Access)。而 <algorithm> 標頭檔定義的 lower_bound() 需要資料結構能被隨機存取(當然,其中資料還需為已排序)才能最佳化為每次搜尋為 O(log n);否則,其將為線性搜尋,即 O(n)。

而 set::lower_bound() 則是利用本身資料結構的特性——其本質是一棵二元搜尋樹(Binary Search Tree),所以搜尋只需 O(log n)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
89 巴幣: 0

創作回應

更多創作