序列分段 - 代码源竞赛平台

题目描述

蜗蜗得到一个长度为 $n$ 的整数序列 $a$。他想把整个序列划分成若干个非空连续段，每个元素必须恰好属于其中一段。

每一段都必须满足两个条件：包含的元素数量不少于 $l$，且这一段中的最大值与最小值之差不超过 $s$。

请你求出最少需要划分成多少段。如果无法完成划分，则输出 $-1$。

输入格式

第一行包含三个整数 $n,s,l$，分别表示序列长度、每一段允许的最大值与最小值之差，以及每一段的最小长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示这个整数序列。

输出格式

输出一行一个整数，表示满足要求的最少段数。如果无法完成划分，输出 $-1$。

样例

4 0 2
1 1 2 2

2

样例解释

可以将序列划分为 $[1,1]$ 和 $[2,2]$ 两段。每段长度都为 $2$，最大值与最小值之差都为 $0$。

整个序列的最大值与最小值之差为 $1$，不能只划分成一段，因此最少需要 $2$ 段。

数据范围

对于 100% 的数据，保证 $1\le n\le 10^5$，$0\le s\le 10^9$，$1\le l\le 10^5$，$-10^9\le a_i\le 10^9$。