解题思路

给定非严格递增数组 $a_1\le a_2\le \cdots \le a_n$，允许至多一次操作：选择区间 $[l,r]$（长度 $L=r-l+1$），对每个 $i\in[l,r]$ 执行

这是一个公差为 $-k$ 的等差增量，左端点的增量最大，为 $kL$。

我们希望操作后数组极差（最大值减最小值）严格大于 $d$，并使所选区间长度 $L$ 最小（可为 $0$，表示不操作）。

关键观察

1. 为了最大化极差，最小值最好保持为原来的最小值 $a_1$。 只要不把下标 $1$ 放进选择的区间，最小值仍是 $a_1$；若包含下标 $1$，最小值只会不变或变大，不利于增大极差。因此最优解一定可以令 $l\ge 2$。

2. 若当前已满足 $a_n-a_1>d$，答案就是 $0$。

3. 否则需要使某个元素超过阈值 $\text{target}=a_1+d+1$。 对于固定左端点 $l(\ge2)$，为了让 $a_l$ 成为新的最大值，只需让

   $$a_l + kL \;>\; a_1 + d,$$

   因而最小需要

   $$L_{\min}(l)=\left\lceil \frac{a_1+d+1-a_l}{k}\right\rceil . $$

   同时区间长度还必须满足 $1\le L_{\min}(l)\le n-l+1$（因为 $r\le n$）。

4. 在所有 $l=2\ldots n$ 中取可行的最小 $L_{\min}(l)$ 即为答案；若不存在可行解，输出 $-1$。

实现方法

• 线性扫描 $l=2\ldots n$，对每个 $l$ 计算上式的 $L_{\min}(l)$，并判断是否不超过可用长度 $n-l+1$。
• 全程使用 64 位整型处理（$d$ 可达 $10^{12}$）。

复杂度分析

• 每组数据只需一次线性扫描：时间复杂度 $O(n)$。
• 只用到常数个变量：空间复杂度 $O(1)$（除输入数组外）。
• 满足 $\sum n \le 2\times 10^5$ 的数据范围。

代码实现

Python

import sys

# 功能函数：返回使极差> d 的最小区间长度（可为0；不可达则-1）
def min_len_exceed(n, d, k, a):
    # 若已满足条件，长度为 0
    if a[-1] - a[0] > d:
        return 0
    target = a[0] + d + 1  # 需要超过的阈值
    INF = 10**18
    ans = INF
    # 选择 l>=2，保证最小值保持为 a[0]
    for l in range(1, n):  # 0-based，对应 l=2..n
        need = target - a[l]
        if need <= 0:
            # 在 a[-1]-a[0] <= d 的前提下，这里通常不会触发
            continue
        Lmin = (need + k - 1) // k  # 向上取整
        if 1 <= Lmin <= n - l:      # 长度不能超过可用位置
            if Lmin < ans:
                ans = Lmin
    return -1 if ans == INF else ans

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    T = next(it)
    out_lines = []
    for _ in range(T):
        n = next(it); d = next(it); k = next(it)
        a = [next(it) for _ in range(n)]
        out_lines.append(str(min_len_exceed(n, d, k, a)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    // 功能函数：计算最小区间长度，不可达则返回 -1
    static long minLenExceed(int n, long d, long k, long[] a) {
        if (a[n - 1] - a[0] > d) return 0; // 已经满足
        long target = a[0] + d + 1;        // 需要超过的阈值
        long ans = Long.MAX_VALUE;

        for (int l = 2; l <= n; l++) {     // l>=2，保持最小值为 a1
            long need = target - a[l - 1];
            if (need <= 0) continue;
            long Lmin = (need + k - 1) / k;        // 向上取整
            long maxLen = n - l + 1;               // 该左端点能取到的最大长度
            if (Lmin >= 1 && Lmin <= maxLen) {
                if (Lmin < ans) ans = Lmin;
            }
        }

        return ans == Long.MAX_VALUE ? -1 : ans;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int T = Integer.parseInt(br.readLine().trim());
        for (int tc = 0; tc < T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            long d = Long.parseLong(st.nextToken());
            long k = Long.parseLong(st.nextToken());
            long[] a = new long[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
            out.append(minLenExceed(n, d, k, a)).append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 功能函数：返回最小区间长度；不可达返回 -1
long long min_len_exceed(int n, long long d, long long k, const vector<long long>& a) {
    if (a[n - 1] - a[0] > d) return 0;      // 已满足
    long long target = a[0] + d + 1;        // 需要超过的阈值
    const long long INF = (1LL<<62);
    long long ans = INF;

    for (int l = 2; l <= n; ++l) {          // 保证最小值 a1 不变
        long long need = target - a[l - 1];
        if (need <= 0) continue;
        long long Lmin = (need + k - 1) / k;    // 向上取整
        long long maxLen = n - l + 1;           // 可用长度上限
        if (Lmin >= 1 && Lmin <= maxLen) {
            ans = min(ans, Lmin);
        }
    }
    return ans == INF ? -1 : ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; long long d, k;
        cin >> n >> d >> k;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        cout << min_len_exceed(n, d, k, a) << "\n";
    }
    return 0;
}

题目内容

给定一个长度为 $n$ 的非严格递增数组 $a_1≤a_2≤...≤a_n$ 。你可以执行以下操作至多一次：

选择区间 $[l,r]$ ，对每个 $i∈[l,r]$ 执行 $a_i←a_i+k×(r-i+1)$ ，其中 $k$ 是给定的固定参数。

请找出能使操作后数组极差(最大值与最小值之差) 超过d 的最小区间长度(可以为 $0$ )。若无法达成，输出 $-1$ 。

【名词解释】

• 极差:数组最大值与最小值的差值，例如数组 {$2,5,7$} 的极差为 $5$ .

输入描述

第一行输入 $T(1 ≦ T ≦ 10^4)$ 表示测试组数。

每组数据包含:

第一行三个整数 $n,d,k(2≦n≦2×10^5,0≦d≦10^{12},1≦k≦10^9)$

第二行 $n$ 个非严格递增整数 $a_1,a_2,...,a_n(1≦a_i≦10^9)$

保证所有测试数据 $\sum n ≦ 2 × 10^5$ 。

输出描述

每组数据输出一个整数，表示满足条件的最小区间长度。

样例1

输入

3
4 5 2
1 3 5 7
3 10 1
2 6 8
3 8 5
1 2 3

输出

0
-1
2