小明正在學習編寫程式控制一個機械人。他發現原來要使該機械人走一條直線都是一件不容易的事。 小明的機械人要在一個 X-Y 平面上沿著 X 的方向走直線。為了要知道該機械人走直線的準確度, 小明在機械人身上加了一個記錄器, 該記錄器可以每隔一定時間記錄機械人的 Y 座標, 設這些記錄為 y0, y2, y3, ..., yt。 若在其中一段連續的記錄 [a,b] 中, 對於所有在 ya, ya+1, ya+2, ..., ya 內的任何 yi 及 yj, |yi - yj| ≤ E 的話 (即在該段記錄內的任何兩個 Y 座標之差的絕對值少於或等於一個預設的容許偏差值 E), 我們就說這機械人在該段時間內能準確地走直線。
小明想知道他的機械人在整個記錄中, 能夠準確地走直線的最長連續記錄是多少?
輸入資料的第一行含有兩個正整數 N 及 E, 它們分別代表記錄的個數及設計的容許偏差值。 隨後的一行上有 N 個整數, 每個整數代表一筆 Y 座標的記錄。 2 ≤ N ≤ 300,000 及 1 ≤ E ≤ 3000
輸出應只有一個正整數, 它代表小明的機械人能夠準確地走直線的最長連續記錄個數。
9 3 0 -4 -2 0 3 1 1 4 5
4
上例中, 有兩段記錄均為最長連續準確走直線記錄 (0, 3, 1, 1 及 3, 1, 1, 4), 他們的記錄個數均為 4 個。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||