步道規劃 (APCS 2026-03 高級)
2.0s 256M把 \(n\) 個地點依座標 \(d_i\) 由小到大排列,再分成恰好 \(k\) 段非空連續區間。每段由左走到右,相鄰兩點的費用是座標差,加上高度增加量的兩倍;下坡不加收費用。段與段之間不行走。只有一點的段費用為 \(0\)。求各段費用最大值的最小可能值。
輸入格式
第一行為 \(n,k\)。第二行為 \(n\) 個座標 \(d_i\),第三行為對應高度 \(h_i\)。
輸出格式
輸出最小可能的最大段費用。
資料範圍
\(1\le k\le n\le10^5\);\(1\le d_i,h_i\le10^9\),所有 \(d_i\) 互異。
評分說明
每筆計分測資獨立計分,每筆 5 分,共 100 分;範例不計分。
範例輸入 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
題目來源
APCS 2026 年 3 月高級實作題第 1 題。
官方未公布題本,題敘參考 ZeroJudge s223「步道規劃」 上的重建版整理,細節可能與正式試題有出入。