解題思路:
雖然題目給的切割點並未排序,但其實我們並不需要自己進行排序,
由於切割點的順序必定是1~ n,
所以我們只需要開一個陣列,把第 i 刀切割點存在陣列第 i - 1 個位置即可。
接下來我們的任務是逐步切割木棍,並計算切割的木棍長度。
要求得木棍長度,很容易想到將木棍上各點位置以 1~ L 表示,
t - h 即是 h 點到 t 點的木棍之長度。
所以我們的任務又變成了:
如何快速尋找目前的已切割的點當中,離當前切割點最近的前後兩點?
實作策略:
熟悉 C++ SLT 和內建函式的話,透過持續加入不重複的元素(題目保證切割點不重複)、
找尋前後元素位置,可以很快想到 set 和 next()、prev()。