d003: 例題 P-1-3. 棍子中點切割
標籤 : Recursion
通過比率 : 496人/549人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-20 15:57

內容

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

輸入一根長度 $L$ 的棍子上面 $N$ 個切割點位置的座標,請計算出切割總成本。

輸入說明

第一行有兩個正整數 $N$ 與 $L$。

第二行有 $N$ 個正整數,依序代表由小到大的切割點座標 $p[1]$~$p[N]$,

數字間以空白隔開,座標的標示的方式是以棍子左端為 $0$, 而右端為$L$。

$N \leq 5 * 10^4$,$L < 10^9$。

輸出說明

切割總成本點。

範例輸入 #1
4 10
1 2 4 6
範例輸出 #1
22
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
提示 :
標籤:
Recursion
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


編號 身分 題目 主題 人氣 發表日期
95
rocky (tim不會寫程式)
d003
注意
1175 2021-11-17 22:15