✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

拼多多-2025.10.26

题目一：图书借阅计划

1️⃣：按顺序处理每个读者的借阅清单

2️⃣：使用布尔数组标记图书是否已被借出

3️⃣：贪心选择优先级最高的可用图书

难度：Low

这道题目的核心是贪心策略。按照固定顺序处理每个读者，对于每个读者按优先级从高到低选择第一本可用图书。通过布尔数组标记图书状态，每次查询和标记都是 O(1) 操作，总时间复杂度为 O(总清单长度)，非常高效。

题目二：密码强度评估

1️⃣：枚举所有可能的半长 k（从大到小）

2️⃣：使用滑动窗口检查每个长度为 2k 的子串

3️⃣：统计冲突对数，冲突为0即可填充成对称密码

难度：Mid

这道题目考察滑动窗口优化技巧。对称密码要求前后两半完全一致，通过枚举半长并检查对应位置是否冲突来判断可行性。滑动窗口技术将时间复杂度优化到 O(n²)，对于 n≤5000 的数据范围完全可以接受。

题目三：货架商品分组

1️⃣：枚举剩余商品数 k（从大到小）

2️⃣：检查总和能否被 k 整除且每段和不小于最大值

3️⃣：贪心验证能否从左到右分成 k 段

难度：Mid

这道题目的关键在于观察到最终剩余 k 个商品时，每个商品价值必为总和除以 k。通过从大到小枚举 k，使用贪心策略验证可行性，找到第一个可行的 k 即为最优解。操作次数为 n-k，时间复杂度 O(n²)。

题目四：视频片段剪辑

1️⃣：使用单调队列维护区间最大值和最小值

2️⃣：动态规划计算最少分段数

3️⃣：用第三个单调队列优化 DP 转移

难度：High

这道题目综合运用了动态规划、滑动窗口和单调队列等多种算法技巧。通过维护三个单调队列分别处理区间极值和 DP 状态转移，将时间复杂度优化到 O(n)。这是一道经典的 DP 优化问题，考察对数据结构的灵活运用。

1. 图书借阅计划

问题描述

K 小姐在图书馆工作，图书馆里有 本图书 和 位读者 。

每位读者都有一份想要借阅的图书清单，清单按照想要借阅的优先级从高到低给出，并且每本图书最多只能借给一位读者。

K 小姐在制定借阅方案，打算依次处理 的借阅清单，并且对于每个清单按优先级从高到低寻找可借阅的图书。如果找到的图书还没有被借出，那么该读者将成功借到这本图书。请问如果按照上述方案，能使得每位读者都成功借到一本图书的话，输出 "YES"，否则输出 "NO"（均不包含双引号）。

输入格式

第一行，包含一个正整数 ，代表测试数据的组数。

对于每组测试数据，分别有 行。

第一行，仅有一个正整数 。

接下来 行，每行先给出一个正整数 ，代表此读者的借阅清单中图书的数量。

接下来给出 个不同的正整数，分别代表按优先级从高到低给出的图书编号 。

保证每组数据中 的总和小于 。

输出格式

对于每组数据，仅输出一行。

如果按照上述方案，可以全部匹配的话，输出 "YES"，否则输出 "NO"（均不包含双引号）。

样例输入

3
4
3 2 3 1
2 1 4
1 3
4 4 1 2 3
5
1 1
1 1
3 1 2 3
2 1 4
2 1 5
4
2 2 1
1 2
1 1
2 3 1

样例输出

YES
NO
NO

数据范围：

• 

• 

• 

• 

• 每组数据中 的总和小于

题解

这道题的核心思想是贪心策略。我们按照读者的顺序依次处理每个人的借阅请求，对于每个读者，按照他的优先级清单从高到低查找，一旦找到一本还没被借出的图书，就立即分配给他。

为什么这个贪心策略是正确的呢？因为题目要求我们按照固定的顺序处理读者，每个读者只需要借到一本图书即可。对于当前读者来说，选择优先级最高的可用图书显然是最优的，这不会影响后续读者的借阅机会。如果某个读者无法借到任何图书，说明方案失败。

具体实现时，我们使用一个布尔数组来标记每本图书是否已被借出。对于每个读者，遍历他的清单，找到第一本未被借出的图书，标记该图书为已借出，并记录成功匹配的次数。如果最终成功匹配的次数等于读者总数 ，说明所有读者都成功借到了图书，输出 "YES"，否则输出 "NO"。

时间复杂度分析：对于每组数据，我们需要遍历所有读者的清单，总共最多 个图书编号，每次查询和标记都是 的操作，因此总时间复杂度为 ，在给定的数据范围内是完全可以接受的。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

T = int(input())
for _ in range(T):
    n = int(input())
    book = [False] * (n + 1)  # 标记图书是否被借出
    cnt = 0  # 成功借阅的读者数
    
    for i in range(n):
        line = list(map(int, input().split()))
        k = line[0]  # 清单中图书数量
        found = False  # 是否成功借到图书
        
        for j in range(1, k + 1):
            bid = line[j]  # 图书编号
            # 如果还没找到且该图书未被借出
            if not found and not book[bid]:
                book[bid] = True  # 标记为已借出
                found = True
                cnt += 1
    
    # 判断是否所有读者都借到图书
    print("YES" if cnt == n else "NO")

• Cpp

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

bool used[10005];  // 标记图书是否被借出

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T, n, k, x;
    cin >> T;
    
    while (T--) {
        cin >> n;
        // 初始化标记数组
        for (int i = 1; i <= n; i++) used[i] = false;
        
        int match = 0;  // 成功匹配数
        
        for (int i = 0; i < n; i++) {
            cin >> k;
            bool flag = false;  // 当前读者是否借到
            
            for (int j = 0; j < k; j++) {
                cin >> x;
                // 如果还没借到且该图书可用
                if (!flag && !used[x]) {
                    used[x] = true;
                    flag = true;
                    match++;
                }
            }
        }
        
        // 输出结果
        cout << (match == n ? "YES" : "NO") << "\n";
    }
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            boolean[] isBorrowed = new boolean[n + 1];  // 标记图书是否被借出
            int success = 0;  // 成功借阅数
            
            for (int i = 0; i < n; i++) {
                int k = sc.nextInt();
                boolean gotBook = false;  // 是否成功借到
                
                for (int j = 0; j < k; j++) {
                    int bookId = sc.nextInt();
                    // 优先级从高到低，选择第一本可用图书
                    if (!gotBook && !isBorrowed[bookId]) {
                        isBorrowed[bookId] = true;
                        gotBook = true;
                        success++;
                    }
                }
            }
            
            // 判断是否所有读者都借到图书
            System.out.println(success == n ? "YES" : "NO");
        }
        
        sc.close();
    }
}

2. 密码强度评估

问题描述

A 先生在开发一个密码强度评估系统。在这个系统中，他定义了一种特殊的"对称密码"：如果一个密码的长度是偶数，并且前一半与后一半完全一致，那么这个密码就是对称密码。例如 "abcabc"、"aaaa" 都是对称密码。特别地，空密码 "" 也被认为是对称密码。

一个密码的对称强度被定义为它的所有子串中，最长的对称密码子串的长度。

例如在密码 "abbc" 中，它的子串为 ["abbc", "abb", "bbc", "ab", "bb", "bc", "a", "b", "c", ""]，而其中对称密码子串为 ["bb", ""]，所以 "abbc" 的对称强度为 "bb" 的长度，即 "abbc" 的对称强度为 。

A 先生发现了一段密码记录，这段记录由 - 组成，但其中某些字符因为记录损坏已经无法辨认，无法辨认的字符使用 "?" 表示。A 先生希望为每个无法辨认的字符 "?" 填入一个字母 -，使得整个密码的对称强度最大。

例如在密码 "aa?ab" 中，可以将 "?" 替换成 "a"，这样填充形成新密码 "aaaab"，其最长对称密码子串为 "aaaa"，对称强度为 。

请帮助 A 先生计算一下填充后的密码最大可能的对称强度是多少？

输入格式

共一行，包括一个字符串 ，其中每个字符均为 - 或者 ? 之一，? 表示无法辨认的字符。字符串长度 满足 。

输出格式

共 行，包含一个整数，表示填充后的密码最大可能的对称强度。

样例输入

aaaaa

jum??ump

dj?aaaaam

样例输出

4

8

6

数据范围：

• 

• 字符串仅包含 - 和 ?

题解

这道题要求找到最长的对称密码子串。对称密码的定义是前一半和后一半完全一致，所以我们可以枚举所有可能的半长 ，然后检查是否存在长度为 的子串可以通过填充 ? 变成对称密码。

关键观察：对于一个长度为 的子串，将其分为前后两半，每一对对应位置 的字符必须满足以下条件之一：

1. 两个字符都是 ?，可以填成任意相同字符
2. 一个是 ?，另一个是字母，? 可以填成该字母
3. 两个都是字母且相同
4. 两个都是字母但不同，这种情况无法形成对称密码

我们从大到小枚举半长 （从 到 ），对于每个 ，检查所有长度为 的子串。为了高效检查，我们使用滑动窗口技术：首先检查起始位置为 的子串，计算有多少对字符是"冲突"的（即情况4）。然后窗口向右滑动，每次移动时更新冲突数：移除最左边的一对，加入最右边的新一对。只要某个窗口的冲突数为 ，说明这个 可行，直接返回 。

时间复杂度：外层枚举 有 个值，对于每个 ，滑动窗口需要 次操作，每次操作 ，总复杂度 。对于 ，这个复杂度是可以接受的。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

s = input()
n = len(s)

# 从大到小枚举半长
for half in range(n // 2, 0, -1):
    bad = 0  # 冲突对数
    
    # 计算起始窗口 [0, 2*half-1] 的冲突数
    for i in range(half):
        a, b = s[i], s[i + half]
        if a != '?' and b != '?' and a != b:
            bad += 1
    
    # 如果无冲突，找到答案
    if bad == 0:
        print(2 * half)
        exit()
    
    # 滑动窗口
    for start in range(1, n - 2 * half + 1):
        # 移除左边的对
        a, b = s[start - 1], s[start - 1 + half]
        if a != '?' and b != '?' and a != b:
            bad -= 1
        
        # 添加右边的对
        a, b = s[start + half - 1], s[start + 2 * half - 1]
        if a != '?' and b != '?' and a != b:
            bad += 1
        
        # 检查是否无冲突
        if bad == 0:
            print(2 * half)
            exit()

# 没有找到，输出0
print(0)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s;
    cin >> s;
    int n = s.size();
    
    // 枚举半长 k，从大到小
    for (int k = n / 2; k > 0; k--) {
        int conf = 0;  // 冲突计数
        
        // 初始窗口 [0, 2k-1]
        for (int i = 0; i < k; i++) {
            char a = s[i], b = s[i + k];
            if (a != '?' && b != '?' && a != b) conf++;
        }
        
        if (conf == 0) {
            cout << 2 * k;
            return 0;
        }
        
        // 滑动窗口
        int limit = n - 2 * k;
        for (int pos = 1; pos <= limit; pos++) {
            // 移除旧对
            char a = s[pos - 1], b = s[pos - 1 + k];
            if (a != '?' && b != '?' && a != b) conf--;
            
            // 添加新对
            a = s[pos + k - 1];
            b = s[pos + 2 * k - 1];
            if (a != '?' && b != '?' && a != b) conf++;
            
            if (conf == 0) {
                cout << 2 * k;
                return 0;
            }
        }
    }
    
    cout << 0;
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        
        // 从大到小枚举半长
        for (int halfLen = n / 2; halfLen > 0; halfLen--) {
            int conflict = 0;  // 冲突对数
            
            // 初始化第一个窗口的冲突数
            for (int i = 0; i < halfLen; i++) {
                char c1 = s.charAt(i);
                char c2 = s.charAt(i + halfLen);
                if (c1 != '?' && c2 != '?' && c1 != c2) {
                    conflict++;
                }
            }
            
            // 如果无冲突，找到答案
            if (conflict == 0) {
                System.out.println(2 * halfLen);
                return;
            }
            
            // 滑动窗口
            int maxStart = n - 2 * halfLen;
            for (int st = 1; st <= maxStart; st++) {
                // 移除左边界的对
                char c1 = s.charAt(st - 1);
                char c2 = s.charAt(st - 1 + halfLen);
                if (c1 != '?' && c2 != '?' && c1 != c2) {
                    conflict--;
                }
                
                // 添加右边界的对
                c1 = s.charAt(st + halfLen - 1);
                c2 = s.charAt(st + 2 * halfLen - 1);
                if (c1 != '?' && c2 != '?' && c1 != c2) {
                    conflict++;
                }
                
                if (conflict == 0) {
                    System.out.println(2 * halfLen);
                    return;
                }
            }
        }
        
        // 没有找到
        System.out.println(0);
        sc.close();
    }
}

3. 货架商品分组

问题描述

小基 在超市管理一排货架，货架上有 个商品从左到右依次排列，记为 。

小基 可以对这个货架进行任意次调整，每次调整可以选择两个相邻的商品，把它们合并成一个新商品（新商品的价值为两个商品价值之和），合并后货架上的商品数量减少 。

小基 想知道，最少需要多少次这样的调整，才能让货架上所有商品的价值都相等。

输入格式

第一行，包含一个正整数 ，代表测试数据的组数。

对于每组测试数据，分别有两行：

第一行，仅有一个正整数 。

第二行，包含 个正整数，分别表示 。

输出格式

对每组测试，输出一个整数，表示使所有剩余商品价值相等所需的最少调整次数。

样例输入

2
4
2 3 3 2
4
10 9 8 7

样例输出

2

3

数据范围：

题解

这道题的关键是理解：如果最终剩下 个商品且它们价值都相等，那么每个商品的价值必定是总和 。而每次合并操作会使商品数量减少1，所以如果最终剩下 个商品，需要的操作次数就是 。为了使操作次数最少，我们需要最大化 。

如何判断能否分成 个价值为 的商品段呢？首先 必须能被 整除，其次 必须不小于最大的单个商品价值（否则无法包含这个商品）。最后，我们需要验证能否通过贪心地从左到右扫描，将数组恰好分成 段，每段和为 。

贪心策略：维护当前段的和，每次加入一个商品，如果和等于目标值 ，就结束这一段，开始新的一段；如果和超过目标值，说明这个 不可行；扫描结束后检查是否恰好分成了 段。

我们从 开始向下枚举（因为 越大，操作次数 越小），找到第一个可行的 即可。

时间复杂度：枚举 最多 次，每次贪心验证需要 ，总复杂度 。但实际上大部分 会因为不能整除或其他条件被快速跳过，实际运行效率较高。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    
    total = sum(a)  # 总价值
    mx = max(a)     # 最大单品价值
    
    ans = n - 1  # 最坏情况：全部合并成一个
    
    # 从大到小枚举剩余商品数 k
    for k in range(n, 0, -1):
        if total % k != 0:
            continue
        
        target = total // k  # 每段目标价值
        if target < mx:
            continue
        
        # 贪心验证能否分成 k 段
        cur = 0     # 当前段的和
        seg = 0     # 已完成的段数
        ok = True
        
        for val in a:
            cur += val
            if cur == target:
                seg += 1
                cur = 0
            elif cur > target:
                ok = False
                break
        
        # 如果成功分成 k 段
        if ok and seg == k:
            ans = n - k
            break
    
    print(ans)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        ll sum = 0, maxv = 0;
        
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            sum += a[i];
            maxv = max(maxv, a[i]);
        }
        
        int res = n - 1;  // 默认全部合并
        
        // 枚举剩余段数 k
        for (int k = n; k >= 1; k--) {
            if (sum % k != 0) continue;
            
            ll tar = sum / k;  // 每段目标值
            if (tar < maxv) continue;
            
            // 贪心检查
            ll cur = 0;
            int cnt = 0;
            bool valid = true;
            
            for (int i = 0; i < n; i++) {
                cur += a[i];
                if (cur == tar) {
                    cnt++;
                    cur = 0;
                } else if (cur > tar) {
                    valid = false;
                    break;
                }
            }
            
            if (valid && cnt == k) {
                res = n - k;
                break;
            }
        }
        
        cout << res << "\n";
    }
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            long[] arr = new long[n];
            long total = 0, maxVal = 0;
            
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextLong();
                total += arr[i];
                maxVal = Math.max(maxVal, arr[i]);
            }
            
            int result = n - 1;  // 最坏情况
            
            // 从大到小枚举剩余段数
            for (int k = n; k >= 1; k--) {
                if (total % k != 0) continue;
                
                long target = total / k;
                if (target < maxVal) continue;
                
                // 贪心验证
                long curSum = 0;
                int segCnt = 0;
                boolean canDo = true;
                
                for (long v : arr) {
                    curSum += v;
                    if (curSum == target) {
                        segCnt++;
                        curSum = 0;
                    } else if (curSum > target) {
                        canDo = false;
                        break;
                    }
                }
                
                if (canDo && segCnt == k) {
                    result = n - k;
                    break;
                }
            }
            
            System.out.println(result);
        }
        
        sc.close();
    }
}

4. 视频片段剪辑

问题描述

小柯正在剪辑一段视频，视频由 个连续的画面帧从左到右依次排列，记为 。

小柯需要将这段视频裁剪成若干连续的片段，用于发布到不同的平台。

视频平台对于上传的视频片段有两个要求：

1. 每段视频中画面帧数值的最大值与最小值之差需要小于等于 。

2. 每段视频的长度需要大于等于 。

小柯需要将该视频全部划分成若干连续的片段，并且使得所有片段都满足平台的要求。小柯想知道，在满足上述条件的情况下，划分后的片段数量最少为多少。如果不能将视频全部划分，那么输出 。

输入格式

第一行，包含一个正整数 ，代表测试数据的组数。

对于每组测试数据，分别有两行：

第一行，有三个正整数 ， ， 。

第二行，包含 个整数，分别表示 。

输出格式

对于每组数据，输出一个整数，代表划分后最少的片段数量。如果不存在符合要求的划分，那么输出 -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. 优化转移：我们需要在所有满足 的 中找到 最小的。使用第三个单调队列维护 的最小值：当 时，将 加入队列；当 时，从队列中移除过期的 。

整个算法的时间复杂度为 ，因为每个元素最多入队出队各一次。

参考代码

• Python

import sys
from collections import deque
input = lambda: sys.stdin.readline().strip()

INF = 10**9

T = int(input())
for _ in range(T):
    n, A, B = map(int, input().split())
    a = [0] + list(map(int, input().split()))  # 下标从1开始
    
    dp = [INF] * (n + 1)
    dp[0] = 0
    
    mx_q = deque()  # 维护最大值
    mn_q = deque()  # 维护最小值
    dp_q = deque()  # 维护dp最小值
    
    left = 1  # 合法左边界
    
    for i in range(1, n + 1):
        # 将 a[i] 加入单调队列
        while mx_q and a[mx_q[-1]] <= a[i]:
            mx_q.pop()
        mx_q.append(i)
        
        while mn_q and a[mn_q[-1]] >= a[i]:
            mn_q.pop()
        mn_q.append(i)
        
        # 调整左边界使得区间满足差值要求
        while mx_q and mn_q and a[mx_q[0]] - a[mn_q[0]] > A:
            if mx_q[0] == left:
                mx_q.popleft()
            if mn_q[0] == left:
                mn_q.popleft()
            left += 1
        
        # 当长度达到B时，将 j=i-B 加入dp队列
        j = i - B
        if j >= 0:
            val = dp[j]
            while dp_q and dp_q[-1][1] >= val:
                dp_q.pop()
            dp_q.append((j, val))
        
        # 移除过期的 j (j < left-1)
        while dp_q and dp_q[0][0] < left - 1:
            dp_q.popleft()
        
        # 计算 dp[i]
        if dp_q:
            dp[i] = dp_q[0][1] + 1
    
    ans = dp[n]
    print(-1 if ans >= INF else ans)

• Cpp

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

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n, A, B;
        cin >> n >> A >> B;
        
        vector<int> a(n + 1);
        vector<int> dp(n + 1, INF);
        
        for (int i = 1; i <= n; i++) cin >> a[i];
        
        dp[0] = 0;
        
        deque<int> mx, mn;  // 最大值、最小值队列
        deque<pair<int, int>> dq;  // (位置, dp值)
        
        int L = 1;  // 左边界
        
        for (int i = 1; i <= n; i++) {
            // 维护最大值队列
            while (!mx.empty() && a[mx.back()] <= a[i]) mx.pop_back();
            mx.push_back(i);
            
            // 维护最小值队列
            while (!mn.empty() && a[mn.back()] >= a[i]) mn.pop_back();
            mn.push_back(i);
            
            // 调整左边界
            while (!mx.empty() && !mn.empty() && a[mx.front()] - a[mn.front()] > A) {
                if (mx.front() == L) mx.pop_front();
                if (mn.front() == L) mn.pop_front();
                L++;
            }
            
            // 将 i-B 加入候选
            int j = i - B;
            if (j >= 0) {
                int v = dp[j];
                while (!dq.empty() && dq.back().second >= v) dq.pop_back();
                dq.push_back({j, v});
            }
            
            // 移除过期
            while (!dq.empty() && dq.front().first < L - 1) dq.pop_front();
            
            // 转移
            if (!dq.empty()) dp[i] = dq.front().second + 1;
        }
        
        int ans = dp[n];
        cout << (ans >= INF ? -1 : ans) << "\n";
    }
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    static final int INF = 1000000000;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            int A = sc.nextInt();
            int B = sc.nextInt();
            
            int[] a = new int[n + 1];
            int[] dp = new int[n + 1];
            Arrays.fill(dp, INF);
            
            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextInt();
            }
            
            dp[0] = 0;
            
            Deque<Integer> maxQue = new ArrayDeque<>();
            Deque<Integer> minQue = new ArrayDeque<>();
            Deque<int[]> dpQue = new ArrayDeque<>();
            
            int leftBd = 1;
            
            for (int i = 1; i <= n; i++) {
                // 维护最大值
                while (!maxQue.isEmpty() && a[maxQue.peekLast()] <= a[i]) {
                    maxQue.pollLast();
                }
                maxQue.addLast(i);
                
                // 维护最小值
                while (!minQue.isEmpty() && a[minQue.peekLast()] >= a[i]) {
                    minQue.pollLast();
                }
                minQue.addLast(i);
                
                // 调整左边界
                while (!maxQue.isEmpty() && !minQue.isEmpty() 
                       && a[maxQue.peekFirst()] - a[minQue.peekFirst()] > A) {
                    if (maxQue.peekFirst() == leftBd) maxQue.pollFirst();
                    if (minQue.peekFirst() == leftBd) minQue.pollFirst();
                    leftBd++;
                }
                
                // 加入新候选
                int j = i - B;
                if (j >= 0) {
                    int val = dp[j];
                    while (!dpQue.isEmpty() && dpQue.peekLast()[1] >= val) {
                        dpQue.pollLast();
                    }
                    dpQue.addLast(new int[]{j, val});
                }
                
                // 移除过期
                while (!dpQue.isEmpty() && dpQue.peekFirst()[0] < leftBd - 1) {
                    dpQue.pollFirst();
                }
                
                // 转移
                if (!dpQue.isEmpty()) {
                    dp[i] = dpQue.peekFirst()[1] + 1;
                }
            }
            
            int ans = dp[n];
            System.out.println(ans >= INF ? -1 : ans);
        }
        
        sc.close();
    }
}