A6885. Strip
编程题
普及+/提高
知识点
题目描述
Alexandra 有一条纸带，上面写有 $n$ 个数字。我们将这些数字从左到右分别记作 $a_{i}$。
现在，Alexandra 希望将这条纸带分割成若干段（也可以只分成一段）。对于每一段纸带，都必须满足下列条件：
- 每一段必须至少包含 $l$ 个数字。
- 每一段中的最大值与最小值之差不得超过 $s$。
请你帮助 Alexandra 找出满足上述条件所需的最少分段数。
现在，Alexandra 希望将这条纸带分割成若干段（也可以只分成一段）。对于每一段纸带，都必须满足下列条件：
- 每一段必须至少包含 $l$ 个数字。
- 每一段中的最大值与最小值之差不得超过 $s$。
请你帮助 Alexandra 找出满足上述条件所需的最少分段数。
输入格式
第一行包含三个用空格隔开的整数 $n, s, l\ (1\le n\le10^5, 0\le s\le10^9, 1\le l\le10^5)$。
第二行包含 $n$ 个用空格隔开的整数 $a_i\ (-10^9\le a_i\le10^9)$。
第二行包含 $n$ 个用空格隔开的整数 $a_i\ (-10^9\le a_i\le10^9)$。
输出格式
输出满足条件的最少分段数。
如果无法分割纸带，则输出 $-1$。
如果无法分割纸带，则输出 $-1$。
输入输出样例
输入 #1
7 2 2 1 3 1 2 4 1 2
输出 #1
3
输入 #2
7 2 2 1 100 1 100 1 100 1
输出 #2
-1
说明/提示
对于第一个样例，可以将纸带分为 $3$ 段：$[1,3,1], [2,4], [1,2]$。
对于第二个样例，无法让 $1$ 和 $100$ 出现在同一段中，因此无解。
对于第二个样例，无法让 $1$ 和 $100$ 出现在同一段中，因此无解。