2376 . 見習魔法師宜恩
TopCoder
Tags
Description
見習魔法師宜恩最近在和他的師父芒果學習水果魔法，他們現在在山上修練。
具體來說，有 $N$ 座山排成一列，由左數來的第 $i$ 座山的高度為 $a_i$，宜恩一開始在第 $1$ 座山上，總共有 $K$ 點魔力值，他的目標是抵達第 $N$ 座山越快越好，這樣他就可以去刷題了。
當宜恩在第 $i$（$1\le i<n$） 座山時他可以做兩種事：
- 花費 $| a_i-a_{i+1}|$ 的時間前進到第 $i+1$ 座山。
- 花費 $1$ 點的魔力值施展水果魔法（水果魔法很厲害所以不需要花費時間），讓第 $i+1$ 座山的高度增加 $1$。需要注意的是芒果在第 $N$ 座山上，他不會被魔法影響所以宜恩沒有辦法讓第 $N$ 座山變高。
宜恩很好奇他需要多少時間才能抵達第 $N$ 座山，請你幫幫他！
Input Format
第一行會有兩個整數 $N$, $K$，代表一共有幾座山跟宜恩的魔力值。
第二行會有一個陣列 $a_1\sim a_N$，代表每座山的高度。
對於所有測試資料：
- $1 \leq N \leq 10 ^ 6 $
- $0 \leq K \leq 10 ^ {18} $
- $0 \leq a_i \leq 10 ^ {12} $
Output Format
輸出一個整數，表示宜恩最少需要花多少時間才能抵達第 $N$ 座山。
Sample Input 1
5 3
4 2 5 1 3
4 2 5 1 3
Sample Output 1
5
Sample Input 2
5 8
6 2 1 3 7
6 2 1 3 7
Sample Output 2
5
Hints
範例測資 1 解釋：其中一種最少時間的方法會使山最後變成$4$ $4$ $5$ $2$ $3$
範例測資 2 解釋：其中一種最少時間的方法會使山最後變成$6$ $5$ $4$ $4$ $7$
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~12 | $N\leq 5000,K\le 2\times 10^ 7,a_i\leq 5000$（$1\leq i\leq N$） | 28 |
| 3 | 1~6, 12~21 | $\exists i$（$1\leq i\leq N$）使得 $a_j\geq a_{j+1}$（$1\leq j< i$），$a_j\leq a_{j+1}$（$i\leq j<N$） | 25 |
| 4 | 0~41 | 無其他限制 | 47 |