題目建置中，歡迎透過表單完善題目。
https://forms.gle/zYDuZnVvweiM3DTC6
---
小明是一位步道規劃師，他正準備在一個連綿的山脈上規劃旅遊路線。山脈上有 $n$ 個觀景點，每個觀景點 $i$ 都有其水平位置 $d_i$ 與海拔高度 $h_i$。
為了方便遊客行走，小明必須從這 $n$ 個觀景點中恰好切分成 $k$ 個連續的步道。
具體規則如下：
-
先將所有觀景點依水平座標 $d_i$ 從小到大排序。
-
將排序後的觀景點序列劃分為 $k$ 個步道，每個步道至少要有一個觀景台。例如：$[P_1 \dots P_{i_1}], [P_{i_1+1} \dots P_{i_2}], \dots, [P_{i_{k-1}+1} \dots P_n]$。
體力值計算方式：
對於同一條步道內的相鄰兩個觀景點 $P_j$ 與 $P_{j+1}$，行走該段路程所需的體力值 $C_j$ 為：
一條步道的總難度，即為該步道內所有路段體力值的總和。若一條步道只包含一個觀景點，其難度為 $0$。
小明希望這 $k$ 條步道中，「難度最大」的那條步道難度盡可能小。請輸出這個最小的難度上限。
範例測資1詳解：
以 $n=5, k=3$ 為例，景點座標與高度排序後如下：
$P_1:(1, 1), P_2:(4, 3), P_3:(8, 10), P_4:(9, 6), P_5:(10, 3)$
相鄰路徑代價：
- $P_1$ 到 $P_2$：$7$
- $P_2$ 到 $P_3$：$18$
- $P_3$ 到 $P_4$：$1$
- $P_4$ 到 $P_5$：$1$
當劃分方式為：
- 段落 1： $\{P_1\}$，體力值 = $0$
- 段落 2： $\{P_2\}$，體力值 = $0$
- 段落 3： $\{P_3, P_4, P_5\}$，體力值 = $1 + 1 = 2$。
最大體力值為 $2$，且總共分成了 $3$ 段。
範例測資2詳解：
以 $n=10, k=3$ 為例，景點座標與高度排序後如下：
$P_1:(1, 10), P_2:(2, 6), P_3:(3, 5), P_4:(4, 3), P_5:(5, 8), P_6:(6, 3), P_7:(7, 8), P_8:(8, 10), P_9:(9, 5), P_{10}:(10, 3)$
相鄰路徑代價：
- $P_1$ 到 $P_2$：$1$
- $P_2$ 到 $P_3$：$1$
- $P_3$ 到 $P_4$：$1$
- $P_4$ 到 $P_5$：$11$
- $P_5$ 到 $P_6$：$1$
- $P_6$ 到 $P_7$：$11$
- $P_7$ 到 $P_8$：$5$
- $P_8$ 到 $P_9$：$1$
- $P_9$ 到 $P_{10}$：$1$
當劃分方式為：
- 段落 1：$\{P_1, P_2, P_3, P_4\}$，體力值 = $1 + 1 + 1 = 3$
- 段落 2：$\{P_5, P_6\}$，體力值 = $1$
- 段落 3：$\{P_7, P_8, P_9, P_{10}\}$，體力值 = $5 + 1 + 1 = 7$
最大體力值為 $7$，且總共分成了 $3$ 段。
第一行包含兩個整數 $n$ 和 $k$ ($1 \le k \le n \le 10^5$)，代表觀景點的數量與分段數。
第二行包含 $n$ 個整數 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$)，保證互不相同。
第三行包含 $n$ 個整數 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$)。
輸出一個整數，代表最小可能的步道難度上限。
5 3 8 1 9 10 4 10 1 6 3 3
2
10 3 2 5 1 6 3 8 4 9 10 7 6 8 10 3 5 10 3 5 3 8
7
公開 測資點#0 (5%): 1.0s , <10M
公開 測資點#1 (5%): 1.0s , <10M
公開 測資點#2 (5%): 1.0s , <10M
公開 測資點#3 (5%): 1.0s , <10M
公開 測資點#4 (5%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <10M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||