P3403.第1题-最小区间长度
题目内容
给定一个长度为 n 的非严格递增数组 a1≦a2≦・・・≦an 。你可以执行至多一次以下操作：
选择区间 [l,r] 对，对每个 i∈[l,r] 执行
- ai←ai+m×(r−i+1) ，换句话说，将下标在 l 到 r 区间内的每一个元素都加上 m×(r−i+1) 。
请求出使得操作后数组存在至少一个位置 1≤j<n 满足 ∣aj−aJ+1∣>d 的最小区间长度(可以为 0 )。若无法实现，输出 −1 。
【名词解释】
非严格递增数组：对于任意 1≦i<n ，都有 ai≦ai+1 。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦104) 代表数据组数，每组测试数据描述如下：
第一行三个整数
n,d,m(2≤n≤2×105,0≤d≤1012,1≤m≤109)
第二行 n 个整数 a1,a2,...,an(1≦ai≦109) ，保证数组非严格递增。
除此之外，保证单个测试文件的 n 之和不超过 2×105 。
输出描述
每组数据输出一个整数，表示满足条件的最小区间长度。
样例1
输入
2
4 3 2
1 2 3 4
3 5 1
2 4 6
输出
2
-1
说明
第一组：其中一种方案为选择区间 [3,4] ，数组变为 {1,2,7,6} ，其中 ∣2−7∣=5>3 满足条件。
样例2
输入
3
2 0 1
1 1
4 0 2
1 2 3 5
6 10 4
1 2 2 4 6 9
输出
1
0
3
