a133:
P-1-3.棍子中點切割
內容
有一台切割棍子的機器，每次將一段棍子會送入此台機器時，機器會偵測棍子上標示的可切割點，然後計算出最接近中點的切割點，並於此切割點將棍子切割成兩段，切割後的每一段棍子都會被繼續送入機器進行切割，直到每一段棍子都沒有切割點為止。請注意，如果最接近中點的切割點有二，則會選擇座標較小的切割點。每一段棍子的切割成本是該段棍子的長度，輸入一根長度L的棍子上面N個切割點位置的座標，請計算出切割總成本。
輸入說明
第一行有兩個正整數N與L。第二行有N個正整數，依序代表由小到大的切割點座標p[1]~p[N]，數字間以空白隔開，座標的標示的方式是以棍子左端為0，而右端為L。N <= 5e4，L< 1e9。
輸出說明
切割總成本點。
範例輸入
#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
公開 測資點#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
提示 ：
第一次會切割在座標 4 的位置，切成兩段 [0, 4], [4, 10]，成本10； [0, 4] 切成 [0, 2] 與 [2, 4]，成本 4； [4, 10] 切成 [4, 6] 與 [6, 10]，成本 6； [0, 2] 切成 [0, 1] 與 [1, 2]；成本 2； 總成本 10+4+6+2 = 22
出處:
ap325
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||