题解

• 题面简述：给定一个非严格递增数组 $a_1 \leq a_2 \leq \cdots \leq a_n$，可以选择一个区间 $[l, r]$ 对每个元素执行一次操作。我们的目标是在操作后使得至少存在一个位置 $1 \leq j < n$ 使得 $|a_j - a_{j+1}| > d$，并求出满足条件的最小区间长度 $r - l + 1$，如果无法实现则输出 $-1$。

• 思路：

  1. 计算相邻差 $x_i = a_{i+1} - a_i$ （对于 $i \in [1, n-1]$）。我们需要检查是否存在满足条件的相邻差。
  2. 若存在 $x_i > d$，则无需操作，答案为 $0$。
  3. 如果不存在这样的相邻差，但存在任何 $x_i + m > d$，或者当 $m > d + \min(x)$ 时，答案为 $1$。
  4. 否则，计算每个可能的
     需满足 $L_i \leq n - (i + 1)$，找出所有可行的 $L_i$ 的最小值。如果没有可行的 $L_i$，则输出 $-1$。

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T; // 输入测试组数
    while (T--) {
        int n;
        long long d, m;
        cin >> n >> d >> m; // 输入 n, d, m
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) 
            cin >> a[i]; // 输入数组元素

        // 计算相邻差
        long long mx = 0, mn = LLONG_MAX;
        bool hasZero = false; // 是否存在大于 d 的相邻差
        vector<long long> gap(n - 1);
        for (int i = 0; i + 1 < n; ++i) {
            long long x = a[i + 1] - a[i];
            gap[i] = x;
            mx = max(mx, x); // 记录最大相邻差
            mn = min(mn, x); // 记录最小相邻差
            if (x > d) hasZero = true; // 判断是否有相邻差大于 d
        }

        // 情况1：原数组已满足
        if (hasZero) {
            cout << 0 << '\n';
            continue;
        }

        // 情况2：长度为1是否可行
        if (mx + m > d || m > d + mn) {
            cout << 1 << '\n';
            continue;
        }

        // 情况3：只能靠左边界累加，计算最小可行 L_i
        long long ans = LLONG_MAX; // 初始化为无穷大
        for (int i = 0; i < n - 1; ++i) {
            long long x = gap[i];
            long long Li = (d - x) / m + 1; // 最小需要的区间长度
            long long maxLenHere = n - (i + 1); // 右侧可用的最大长度
            if (Li <= maxLenHere) 
                ans = min(ans, Li);
        }

        cout << (ans == LLONG_MAX ? -1 : ans) << '\n'; // 输出结果
    }
    return 0;
}

Python

import sys

def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    T = int(next(it))
    out = []
    
    for _ in range(T):
        n = int(next(it))
        d = int(next(it))
        m = int(next(it))
        a = [int(next(it)) for _ in range(n)]

        # 计算相邻差
        mx = 0
        mn = float('inf')
        hasZero = False
        gap = []

        for i in range(n - 1):
            x = a[i + 1] - a[i]
            gap.append(x)
            mx = max(mx, x)
            mn = min(mn, x)
            if x > d:
                hasZero = True

        # 情况1：原数组已满足
        if hasZero:
            out.append("0")
            continue

        # 情况2：长度为1是否可行
        if mx + m > d or m > d + mn:
            out.append("1")
            continue

        # 情况3：只能靠左边界累加
        ans = float('inf')
        for i in range(n - 1):
            x = gap[i]
            Li = (d - x) // m + 1
            maxLenHere = n - (i + 1)
            if Li <= maxLenHere:
                ans = min(ans, Li)

        out.append(str(-1 if ans == float('inf') else ans))

    print("\n".join(out))

if __name__ == "__main__":
    solve()

Java

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

public class Main {
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        FastScanner(InputStream is) { br = new BufferedReader(new InputStreamReader(is)); }
        String next() throws IOException {
            while (st == null || !st.hasMoreElements()) {
                String line = br.readLine();
                if (line == null) return null;
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }
        long nextLong() throws IOException { return Long.parseLong(next()); }
        int nextInt() throws IOException { return Integer.parseInt(next()); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int T = fs.nextInt(); // 输入测试组数
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            int n = fs.nextInt();
            long d = fs.nextLong();
            long m = fs.nextLong();
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = fs.nextLong();

            // 计算相邻差
            long mx = 0, mn = Long.MAX_VALUE;
            boolean hasZero = false;
            long[] gap = new long[n - 1];

            for (int i = 0; i + 1 < n; i++) {
                long x = a[i + 1] - a[i];
                gap[i] = x;
                if (x > mx) mx = x;
                if (x < mn) mn = x;
                if (x > d) hasZero = true; // 判断是否有相邻差大于 d
            }

            // 情况1：原数组已满足
            if (hasZero) {
                sb.append(0).append('\n');
                continue;
            }

            // 情况2：长度为1可行
            if (mx + m > d || m > d + mn) {
                sb.append(1).append('\n');
                continue;
            }

            // 情况3：只能靠左边界累加
            long ans = Long.MAX_VALUE; // 初始化为无穷大
            for (int i = 0; i < gap.length; i++) {
                long x = gap[i];
                long Li = (d - x) / m + 1; // 最小需要的区间长度
                long maxLenHere = n - (i + 1); // 右侧可用的最大长度
                if (Li <= maxLenHere) ans = Math.min(ans, Li);
            }

            sb.append(ans == Long.MAX_VALUE ? -1 : ans).append('\n');
        }

        System.out.print(sb.toString());
    }
}

题目内容

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

选择区间 $[l,r]$ 对，对每个 $i∈[l,r]$ 执行

• $a_i←a_i+m×(r-i+1)$ ，换句话说，将下标在 $l$ 到 $r$ 区间内的每一个元素都加上 $m×(r-i+1)$ 。

请求出使得操作后数组存在至少一个位置 $1≤j<n$ 满足 $|a_j-a_{J+1}|>d$ 的最小区间长度(可以为 $0$ )。若无法实现，输出 $-1$ 。

【名词解释】

非严格递增数组：对于任意 $1 ≦i< n$ ，都有 $a_i≦ a_{i+1}$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦T ≦ 10^4)$ 代表数据组数，每组测试数据描述如下：

第一行三个整数

$n,d,m(2≤n≤2×10^5,0≤d≤10^{12},1≤m≤10^9)$

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

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

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

样例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