「和尚端湯上塔堂，塔滑湯灑湯燙塔。」
現在有很多和尚要進行端湯任務，可是若和尚們把湯灑成一團，會害整個場面慘不忍睹，因此你決定規劃出若干個不會讓他們把湯灑出來的任務派送給若干個和尚來讓他們進行端湯任務。
所謂端湯任務，就是要讓和尚從 n 座排成一直線的高塔中，選出一個區間 [l, r] ( 1 ≤ l ≤ r ≤ n ) 讓和尚將湯從 l 端到 r。但你知道若這個區間的高度全距，也就是最高的高塔和最低的高塔的高度差，超過 k 的話，和尚就會因為崎嶇的路線而把湯灑出來。
你希望能夠讓盡量多的和尚做到任務，但又不希望有兩個和尚做到同樣的任務(也就是選出來的區間一樣)，也不希望有和尚在任務中把湯灑出來，請問你至多能讓幾個和尚進行端湯任務呢?
每筆測資的輸入共有兩行。
第一行有兩個正整數 n 與 k，代表高塔的個數以及和尚不會把湯灑出來的高度全距極限，兩數字以一空白間隔。
接下來的一行包含 n 個正整數 h1 ∼ hn，代表由左數過來第 i 座高塔的高度是 hi。
1. 對於所有的 i 都滿足， 1 ≤ hi ≤ 109。
2. 1 ≤ k ≤ 109。
請輸出一個非負整數，代表你最多可以讓幾個和尚進行端湯任務。
#test input 1: 6 6 1 7 3 8 2 1 #test input 2: 5 1 1 2 3 1 2
#test output 1: 15 #test output 2: 8
greedy, two pointers, data structures (CF 2200)
6% 的測資滿足 1 ≤ n ≤ 500。
19% 的測資滿足 1 ≤ n ≤ 5000。
28% 的測資滿足 1 ≤ n ≤ 500000，且對於所有滿足 1 ≤ i < n 的 i ，都滿足 hi ≤ hi+1。
47% 的測資滿足 1 ≤ n ≤ 500000。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||