#45928: 解題思路


henry.rem.rem@gmail.com (*ฅ́˘ฅ̀*)

學校 : 臺北市立松山高級中學
編號 : 278368
來源 : [1.161.41.35]
最後登入時間 :
2025-05-05 21:10:22
f607. 3. 切割費用 -- 2021年1月APCS | From: [1.161.43.97] | 發表日期 : 2025-04-29 23:59

解題思路:

雖然題目給的切割點並未排序,但其實我們並不需要自己進行排序,

由於切割點的順序必定是1~ n,

所以我們只需要開一個陣列,把第 i 刀切割點存在陣列第 i - 1 個位置即可。

接下來我們的任務是逐步切割木棍,並計算切割的木棍長度。

要求得木棍長度,很容易想到將木棍上各點位置以 1~ L 表示,

t - h 即是 h 點到 t 點的木棍之長度。

所以我們的任務又變成了:

如何快速尋找目前的已切割的點當中,離當前切割點最近的前後兩點?

實作策略:

熟悉 C++ SLT 和內建函式的話,透過持續加入不重複的元素(題目保證切割點不重複)、

找尋前後元素位置,可以很快想到 set 和 next()、prev()。

範例解法

 
ZeroJudge Forum