從莎朗大街的街頭走到街尾,依序會經過 $n$ 棟大樓,其高度分別為 $h_1, h_2, \ldots, h_n$。每棟大樓的頂樓都是停機坪,對每個 $k \in \{ 1, 2, \ldots, n \}$,第 $k$ 為飛行員想要從第 $i_k$ 棟大樓駕駛直升機飛到第 $j_k$ 棟大樓,其中 $1 \leq i_k < j_k \leq n$。她的飛行方式如下:先從第 $i_k$ 棟大樓向上直升至被稱為 $x_{i_k, j_k}$ 的高度,接著在高度不變的情況下,向街尾飛至第 $j_k$ 大樓上方,最後降落在第 $j_k$ 棟大樓的頂端。為了避免撞到大樓,$x_{i_k, j_k}$ 不應小於 $h_{i_k} + 1$、$h_{i_k+1} + 1$、$h_{i_k+2} + 1$、$\ldots$、$h_{j_k} + 1$ 中的任一個,為了省油,應盡量小,因此我們希望 $x_{i_k, j_k}$ 恰為 $h_{i_k} + 1$、$h_{i_k+1} + 1$、$h_{i_k+2} + 1$、$\ldots$、$h_{j_k} + 1$ 的最小值。
子任務(測資) | 額外限制 | 分數 |
1 | $n \leq 10$ | 10 |
2 | $n \leq 1000000$ | 90 |
對每個$k \in \{ 1, 2, \ldots, n \}$,輸出的第 $k$ 行為$x_{i_k, j_k}$。
8 3 2 5 7 3 1 4 5 2 5 1 4 3 8 6 7 3 6 4 5 2 7 3 5
3 3 2 2 2 4 2 4
本題出自2018 TOI Pre
(TIOJ 2055)
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |