f626: 浩杰的紅豆冰
Tags : 區間 紅豆冰
Accepted rate : 13人/16人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-16 20:26

Content

浩杰喜歡吃又紅又冰的紅豆冰,尤其是呂家紅豆冰和傑人紅豆冰(註1),但是浩杰是一位歌手,他知道吃紅豆冰會影響到他的聲音,所以他不敢亂吃未知紅冰程度(註2)的紅豆冰。

現在浩杰面前有N碗紅豆冰,他想吃K碗,但又希望這K碗中的紅冰程度差(註3)不要超過G,他能看出每一碗的紅冰程度,但是實在是太多碗紅豆冰了,他沒有辦法直接判斷哪幾碗的紅冰程度差符合他的理想,再加上離他下一場演唱會的時間已經不多了,所以他只能選擇連續的K碗,否則會來不及。現在浩杰希望你可以寫個程式幫幫他。

 

註1:傑人紅豆冰店的老闆希望他所有的顧客都能成為傑出的人,便為他的店取此名。

註2:紅冰程度是指一碗紅豆冰的冰度和甜度經某種公式計算後得到的數值,不同的紅冰程度會對浩杰的聲音造成不同程度的影響。

註3:紅冰程度差是指某些紅豆冰中紅冰程度最高那碗與紅冰程度最低那碗的紅冰程度的差值。

Input

測資為單筆輸入。

第一行有三個以空白隔開的正整數N、K、G。(N≤10^6、K≤10^4、G<2^31)

第二行有N個以空白隔開的正整數Pi,代表每一碗紅豆冰的紅冰程度。(Pi<2^31)

Output

請輸出一個正整數A,代表總共有A組的紅豆冰符合浩杰的理想。

Sample Input #1
10 3 5
4 2 9 8 6 10 7 9 5 3 
Sample Output #1
5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
Hint :

範例測資中,符合浩杰理想的5組分別為:9,8,6(紅冰程度差為3)、8,6,10(紅冰程度差為4)、6,10,7(紅冰程度差為4)、10,7,9(紅冰程度差為3)、7,9,5(紅冰程度差為4)。

 

如果題目太爛或有出錯,還請不吝告知,感謝!

Tags:
區間 紅豆冰
出處:
wseds [管理者:
yes51851823@... (wseds)
]


ID User Problem Subject Hit Post Date
24224
711004@stu.c... (牟宗晞)
f626
extra
65 2021-01-28 18:40
24219
fire5386 (皮卡丘)
f626
線段樹
49 2021-01-28 17:42