時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
每個觀景點有水平位置 dᵢ 與高度 hᵢ。先依 dᵢ 遞增排序，再把點序列分成恰好 K 個非空連續區段，作為 K 條步道。同一段內相鄰點 j、j+1 的費力值為 (d[j+1]−d[j])+max(0,2×(h[j+1]−h[j]))，步道難度是這些費力值的總和；單點步道難度為 0。不同步道之間的路段不計費力值。求所有步道中最大難度能達到的最小值。
輸入格式
第一行為 N、K，1 ≤ K ≤ N ≤ 100000。第二行為 N 個互不相同的水平位置，第三行為對應的 N 個高度；位置與高度皆介於 1 與 10^9。
輸出格式
輸出最小可能的最大步道難度。
範例測資
範例輸入 1
5 3 8 1 9 10 4 10 1 6 3 3
範例輸出 1
2
範例輸入 2
10 3 2 5 1 6 3 8 4 9 10 7 6 8 10 3 5 10 3 5 3 8
範例輸出 2
7
請先登入後再提交程式碼
討論與題解
載入討論區…