例題 P-1-3. 棍子中點切割


提交答案

分數: 100 (部分)
時間限制: 1.0s
記憶體限制: 1G

作者:
題目類型

有一台切割棍子的機器,每次將一段棍子會送入此台機器時,機器會偵測棍子上標示 的可切割點,然後計算出最接近中點的切割點,並於此切割點將棍子切割成兩段,切割後的每一段棍子都會被繼續送入機器進行切割,直到每一段棍子都沒有切割點為止。請注意,如果最接近中點的切割點有二,則會選擇座標較小的切割點。每一段棍子的切割成本是該段棍子的長度, 輸入一根長度 L 的棍子上面 N 個切割點位置的座標,請計算出切割總成本。

輸入格式

第一行有兩個正整數 NL。 第二行有 N 個正整數,依序代表由小到大的切割點座標 p[1] p[N], 數字間以空白隔開,座標的標示的方式是以棍子左端為 0, 而右端為LN5104L<109

輸出格式

切割總成本點。

範例輸入

複製
4 10
1 2 4 6

範例輸出

複製
22

留言

目前沒有評論。