17. Lacy 的鬧鐘

0 Judge

Code: 0


Lacy 的鬧鐘

題目敘述

Lacy 很會賴床所以設定了 n 個鬧鐘每天會在固定的時間啟動, 響一分鐘然後停止。然而明天是放假日, Lacy 為了睡好睡滿, 需要關掉一些鬧鐘。 他知道, 如果在 m 分鐘內有 k 分鐘有鬧鐘響起, 他就會醒來。為了早點睡覺 Lacy 想要知道最少要關掉幾個鬧鐘, 才能確保明天不會被鬧鐘吵醒。

輸入說明

輸入的第一行包含一個整數 $T(T\leq 20)$,代表接下來有 $T$ 組測試資料。每組測試資料的第1行是3個正整數 n,m,k $( 1 \leq n \leq 10000, 1 \leq m,k \leq 1000000)$, 接著一行有 n 個非嚴格遞增的正整數, 第 i 個數 $a_i ( 1 \leq a_i \leq 1000000 )$ 表示鬧鐘 i 會在第 $a_i$ 分鐘開始時響起。另外 Lacy 的世界一天有 $10^7$ 秒。

輸出說明

對於每個測試資料輸出一行, 表示最少需要關掉多少鬧鐘。

範例輸入

範例輸出

子題一[20%]

$a_i=i$

子題二[30%]

$n \leq 100$

子題三[50%]

無額外限制


Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 3