解题思路

• 本题需要把数组划分成若干连续段，使每段满足：

  1. 段内最大值与最小值之差 ≤ A；
  2. 段长 ≥ B； 并使段数最少。

• 关键算法：

  1. 双指针 + 单调队列：用两个单调队列维护滑动窗口的最大值与最小值。右指针向右扩，若当前窗口不满足 max-min ≤ A，左指针右移并在队头弹出过期下标。这样可在 O(n) 得到对每个右端点 i 的“最左合法起点” L(i)（0-based）。

  2. 动态规划 + 区间最小值的单调队列：令 dp[i] 为前 i 个元素（1-based）最少段数，dp[0]=0； 若选一段以 i 结尾，起点 s 需满足 s ∈ [L(i-1), i-B]（$0-based$对应的前缀切分点 j=s，范围为 [L(i-1), i-B]）。 则

     $dp[i]$ = $1$ + $\min_{j \in [L(i-1),\, i-B]} dp[j]$

其中 j 的有效区间左右端点均随 i 单调移动，故可用另一条单调队列维护这段区间内 dp[j] 的滑动最小值，整体仍为 O(n)。

• 流程小结：

  • 用两条单调队列维护 max/min，移动确定每个 i 的最左合法 L；
  • 同步用一条单调队列维护区间 [L, i-B] 上的 dp 最小值，得到 dp[i]；
  • 答案为 dp[n]，若不可达输出 -1。

复杂度分析

• 时间复杂度：每个元素至多进出各队列一次，O(n)。
• 空间复杂度：dp 与若干队列，O(n)。

代码实现

Python

# 题意函数写在外部，主函数只做输入输出
# 使用双指针+单调队列维护区间max/min；再用单调队列维护dp的区间最小值

import sys
from collections import deque

INF = 10 ** 9

def min_segments(n, A, B, a):
    # dp[i]: 前 i 个元素(1-based)的最少段数；dp[0]=0
    dp = [INF] * (n + 1)
    dp[0] = 0

    # 维护窗口 [L..i-1] 的最大/最小值下标（0-based）
    dq_max, dq_min = deque(), deque()
    L = 0  # 当前窗口最左可行下标(0-based)

    # 维护可选切分点 j 的滑动区间 [L, i-B] 上 dp[j] 的单调队列
    cand = deque()  # 存 j 下标，保持 dp[j] 递增

    for i in range(1, n + 1):
        idx = i - 1  # 新加入的元素下标(0-based)

        # 插入最大值队列（保持从大到小）
        while dq_max and a[dq_max[-1]] <= a[idx]:
            dq_max.pop()
        dq_max.append(idx)

        # 插入最小值队列（保持从小到大）
        while dq_min and a[dq_min[-1]] >= a[idx]:
            dq_min.pop()
        dq_min.append(idx)

        # 收缩左端，直到满足 max - min <= A
        while dq_max and dq_min and a[dq_max[0]] - a[dq_min[0]] > A:
            L += 1
            # 弹出过期下标
            if dq_max and dq_max[0] < L:
                dq_max.popleft()
            if dq_min and dq_min[0] < L:
                dq_min.popleft()

        # 当前右端 i(1-based)，可加入新的右边界切分点 j = i - B（0-based）
        r = i - B
        if r >= 0:
            # cand 维持 dp[j] 的单调递增
            while cand and dp[cand[-1]] >= dp[r]:
                cand.pop()
            cand.append(r)

        # 合法区间的左边界为 L（0-based），即 j >= L
        while cand and cand[0] < L:
            cand.popleft()

        if cand:
            dp[i] = dp[cand[0]] + 1  # 选择区间内最优 j

    return dp[n] if dp[n] < INF else -1


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t = data[0]
    p = 1
    out = []
    for _ in range(t):
        n, A, B = data[p], data[p+1], data[p+2]
        p += 3
        a = data[p:p+n]
        p += n
        out.append(str(min_segments(n, A, B, a)))
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main，ACM 风格。使用双指针+单调队列与DP滑动最小值。
import java.io.*;
import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;

    // 计算最少段数
    static int minSegments(int n, long A, int B, long[] a) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        Deque<Integer> dqMax = new ArrayDeque<>(); // 维护最大值下标
        Deque<Integer> dqMin = new ArrayDeque<>(); // 维护最小值下标
        int L = 0; // 当前窗口最左可行下标(0-based)

        Deque<Integer> cand = new ArrayDeque<>(); // 维护区间 [L, i-B] 上 dp[j] 的单调队列

        for (int i = 1; i <= n; i++) {
            int idx = i - 1;

            // 插入最大值队列（保持从大到小）
            while (!dqMax.isEmpty() && a[dqMax.peekLast()] <= a[idx]) dqMax.pollLast();
            dqMax.offerLast(idx);

            // 插入最小值队列（保持从小到大）
            while (!dqMin.isEmpty() && a[dqMin.peekLast()] >= a[idx]) dqMin.pollLast();
            dqMin.offerLast(idx);

            // 收缩左端，直到满足 max - min <= A
            while (!dqMax.isEmpty() && !dqMin.isEmpty() && a[dqMax.peekFirst()] - a[dqMin.peekFirst()] > A) {
                L++;
                if (!dqMax.isEmpty() && dqMax.peekFirst() < L) dqMax.pollFirst();
                if (!dqMin.isEmpty() && dqMin.peekFirst() < L) dqMin.pollFirst();
            }

            // 加入新的右边界切分点 j = i - B（0-based）
            int r = i - B;
            if (r >= 0) {
                while (!cand.isEmpty() && dp[cand.peekLast()] >= dp[r]) cand.pollLast();
                cand.offerLast(r);
            }

            // 弹出不在合法区间左边界之前的下标
            while (!cand.isEmpty() && cand.peekFirst() < L) cand.pollFirst();

            if (!cand.isEmpty()) {
                dp[i] = dp[cand.peekFirst()] + 1;
            }
        }

        return dp[n] >= INF ? -1 : dp[n];
    }

    // 简单高效读入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
        long nextLong() throws IOException {
            int c, sgn = 1;
            long x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
    }

    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 A = fs.nextLong();
            int B = fs.nextInt();
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = fs.nextLong();
            sb.append(minSegments(n, A, B, a)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// ACM 风格：主函数读入，功能函数在外部。
// 算法：双指针+单调队列维护区间 max/min；DP + 单调队列维护区间最小值。
#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

int minSegments(int n, long long A, int B, const vector<long long>& a) {
    vector<int> dp(n + 1, INF);
    dp[0] = 0;

    deque<int> dqMax, dqMin; // 维护窗口内最大/最小值的下标
    int L = 0;               // 当前窗口最左可行下标(0-based)

    deque<int> cand;         // 维护 [L, i-B] 区间内 dp[j] 的单调队列（dp 值递增）

    for (int i = 1; i <= n; i++) {
        int idx = i - 1;

        // 插入最大值队列（从大到小）
        while (!dqMax.empty() && a[dqMax.back()] <= a[idx]) dqMax.pop_back();
        dqMax.push_back(idx);

        // 插入最小值队列（从小到大）
        while (!dqMin.empty() && a[dqMin.back()] >= a[idx]) dqMin.pop_back();
        dqMin.push_back(idx);

        // 收缩左端直到满足 max - min <= A
        while (!dqMax.empty() && !dqMin.empty() && a[dqMax.front()] - a[dqMin.front()] > A) {
            L++;
            if (!dqMax.empty() && dqMax.front() < L) dqMax.pop_front();
            if (!dqMin.empty() && dqMin.front() < L) dqMin.pop_front();
        }

        // 右边界新增候选切分点 j = i - B（0-based）
        int r = i - B;
        if (r >= 0) {
            while (!cand.empty() && dp[cand.back()] >= dp[r]) cand.pop_back();
            cand.push_back(r);
        }

        // 弹出左侧越界的候选 j
        while (!cand.empty() && cand.front() < L) cand.pop_front();

        if (!cand.empty()) {
            dp[i] = dp[cand.front()] + 1;
        }
    }

    return dp[n] >= INF ? -1 : dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, B;
        long long A;
        cin >> n >> A >> B;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        cout << minSegments(n, A, B, a) << "\n";
    }
    return 0;
}

题目内容

多多正在处理一批数据,需要把一条长度为 $n$ ,从左到右依次排列的数组 $a_1,a_2,…,a_n$ 裁剪成若干连续的数据段,用于录入公司的数据分析系统.

数据分析系统对于录入的数据块有两个要求

1.每段数据中的最大值与最小值之差需要 小于等于 $A$ .

2.每段数据的长度需要 大于等于 $B$ .

多多需要将该数组全部划分成若干连续的数据段，并且使得所有数据段都满足数据分析系统的要求.多多想知道,在满足上述条件的情况下,划分后的数据段的数量最少为多少,如果不能将数组全部划分,那么输出 $-1$ .

输入描述

第一行,包含一个正整数 $T(1 ≤ T≤ 3)$ 代表测试数据的组数

对于每组测试数据,分别有两行:

第一行,有三个正整数 $n(1 ≤n≤ 10^5),A(0≤ A≤10^9),B(1 ≤ B≤ 10^5)$ .

第二行,包含 $n$ 个整数,分别表示 $a_1,a_2,...,a_n(-10^9≤a_i≤ 10^9)$

输出描述

对于每组数据,输出一个正整数,代表划分后最少的数据段的数量,如果不存在符合要求的划分,那么输出 -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)$

对于第二组数据,无法找出符合要求的划分.