P4311.第4题-数据分析系统
题目内容
多多正在处理一批数据,需要把一条长度为 n ,从左到右依次排列的数组 a1,a2,…,an 裁剪成若干连续的数据段,用于录入公司的数据分析系统.
数据分析系统对于录入的数据块有两个要求
1.每段数据中的最大值与最小值之差需要 小于等于 A .
2.每段数据的长度需要 大于等于 B .
多多需要将该数组全部划分成若干连续的数据段，并且使得所有数据段都满足数据分析系统的要求.多多想知道,在满足上述条件的情况下,划分后的数据段的数量最少为多少,如果不能将数组全部划分,那么输出 −1 .
输入描述
第一行,包含一个正整数 T(1≤T≤3) 代表测试数据的组数
对于每组测试数据,分别有两行:
第一行,有三个正整数 n(1≤n≤105),A(0≤A≤109),B(1≤B≤105) .
第二行,包含 n 个整数,分别表示 a1,a2,...,an(−109≤ai≤109)
输出描述
对于每组数据,输出一个正整数,代表划分后最少的数据段的数量,如果不存在符合要求的划分,那么输出 -1.
样例1
输入
2
10 5 1
1 2 3 4 5 6 7 8 9 10
5 3 3
10 6 2 4 -1
输出
2
-1
说明
对于第一组数据,可以最少划分为两个数据段:
(1,2,3,4,5)(6,7,8,9,10)
对于第二组数据,无法找出符合要求的划分.
