突击期的最大里程 题解

题目分析

我们需要在给定的 $N$ 天行军记录中，找出所有长度为 $W$ 的连续子数组，并要求该子数组内任意相邻两天的里程差的绝对值不超过 $D$。符合这一条件的子数组被称为“合格的突击期”。目标是在所有合格突击期中，计算出 $W$ 天里程总和的最大值；若不存在则输出 $-1$。

数据的规模较大：$N$ 可达 $10^5$，$W$ 也可达 $10^5$。如果采用朴素的枚举方法，对于每一个窗口都重新检查内部所有相邻对的差值，复杂度会达到 $O(N \times W)$，在最坏情况下无法通过。

解题思路

1. 前缀和快速求和

为了快速计算任意窗口 $[L, R]$ 的里程总和，我们可以预处理前缀和数组：

• $prefix[i]$ 表示前 $i$ 天（下标 $1 \sim i$）的里程总和。
• 窗口和可表示为 $prefix[R] - prefix[L-1]$。

2. 转化条件：用差值数组表示“颠簸”

对于相邻两天的约束，我们可以预处理一个差值数组 $diff$，其中 $diff[i] = |a[i] - a[i-1]|\ (2 \le i \le N)$。
那么，一个长度为 $W$ 的窗口 $[L, R]$（其中 $R = L + W - 1$）是合格的，当且仅当这个窗口内所有相邻对的差值都不超过 $D$。在 $diff$ 数组上，就等价于区间 $[L+1, R]$ 中的最大值不超过 $D$。

3. 滑动窗口 + 计数器维护合法状态

直接求区间最大值可以用线段树、ST表或单调队列，但本题有更简洁的线性做法。

我们维护一个变量 bad，表示当前窗口内有多少个相邻对的差值大于 $D$。当窗口滑动时：

• 如果移出窗口的那个相邻对是不合格的（即它的 $diff>D$），则 bad 减 1。
• 如果新加入窗口的那个相邻对是不合格的，则 bad 加 1。
• 窗口合格当且仅当 bad == 0。

注意：

• 当 $W = 1$ 时，窗口内没有相邻对，任何单天都自然合格。
• 初始窗口需要单独计算一次 bad，然后通过滑动依次更新。

算法步骤

1. 读入 $N, W, D$ 和数组 $a$。
2. 若 $W = 1$，直接输出数组中的最大值，算法结束。
3. 计算前缀和数组 $prefix$（长度为 $N+1$，$prefix[0]=0$）。
4. 构建差值数组 $diff$，大小为 $N-1$，$diff[i] = |a[i]-a[i-1]|$（下标从 $1$ 开始对应 $a_1$ 与 $a_0$ 的差，可根据习惯调整）。
5. 初始化 bad = 0，遍历第一个窗口 $[0, W-1]$ 中的所有相邻对，统计 $diff>D$ 的数量。
6. 如果初始窗口 bad == 0，则更新答案 $maxSum = prefix[W] - prefix[0]$；否则 $maxSum$ 保持初值 $-1$。
7. 滑动窗口：窗口左端点从 $1$ 移动到 $N-W$。
   • 移除左端点的相邻对：若该相邻对原来是不合格的（$diff[L]>D$），则 bad--。
   • 加入右端点的相邻对：新窗口的最后一个相邻对是 $a[R]$ 与 $a[R-1]$，其中 $R = L+W-1$。若 $diff[R]>D$，则 bad++。
   • 若 bad == 0，则用当前窗口和尝试更新 $maxSum$。
8. 输出 $maxSum$。

时间复杂度分析

• 预处理前缀和与差值数组：$O(N)$。
• 初始窗口统计：$O(W)$。
• 滑动窗口共移动 $N-W$ 次，每次更新 $O(1)$。
• 整体时间复杂度为 $O(N)$，可以完美通过 $N \le 10^5$ 的数据。

空间复杂度：需要存储数组 $a$、前缀和以及 $diff$，均为 $O(N)$。

参考代码（优化后的线性解法）

cpp
复制
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int main() {
7    ios::sync_with_stdio(false);
8    cin.tie(nullptr);
9
10    int N, W;
11    long long D;
12    cin >> N >> W >> D;
13
14    vector<long long> a(N);
15    for (int i = 0; i < N; ++i) {
16        cin >> a[i];
17    }
18
19    // 特判：W == 1，任意单天都合格，输出最大值
20    if (W == 1) {
21        cout << *max_element(a.begin(), a.end()) << endl;
22        return 0;
23    }
24
25    // 前缀和
26    vector<long long> pref(N + 1, 0);
27    for (int i = 0; i < N; ++i) {
28        pref[i + 1] = pref[i] + a[i];
29    }
30
31    // 差值数组 diff[i] = |a[i] - a[i-1]|，i 从 1 到 N-1
32    // 为了方便，这里将 diff 的下标与右端点对齐，即 diff[i] 表示 a[i] 与 a[i-1] 的差
33    vector<long long> diff(N);
34    for (int i = 1; i < N; ++i) {
35        diff[i] = abs(a[i] - a[i - 1]);
36    }
37
38    // 统计初始窗口 [0, W-1] 中的不合格相邻对
39    int bad = 0;
40    for (int i = 1; i < W; ++i) {
41        if (diff[i] > D) ++bad;
42    }
43
44    long long maxSum = -1;
45    if (bad == 0) {
46        maxSum = pref[W] - pref[0];
47    }
48
49    // 滑动窗口，窗口左端点 L 从 1 到 N-W
50    for (int L = 1; L + W - 1 < N; ++L) {
51        int R = L + W - 1;
52
53        // 移出窗口的相邻对：a[L-1] 与 a[L] 的差（对应 diff[L]）
54        if (diff[L] > D) --bad;
55        // 加入窗口的相邻对：a[R-1] 与 a[R] 的差（对应 diff[R]）
56        if (diff[R] > D) ++bad;
57
58        if (bad == 0) {
59            long long sum = pref[R + 1] - pref[L];
60            if (sum > maxSum) maxSum = sum;
61        }
62    }
63
64    cout << maxSum << endl;
65    return 0;
66}

代码说明

• 使用 ios::sync_with_stdio(false); cin.tie(nullptr); 来加速输入输出，应对大数据量。
• 前缀和数组 pref 的长度为 $N+1$，pref[i] 表示前 $i$ 天的里程和，并利用它快速计算窗口和。
• 差值数组 diff 记录相邻天的绝对差，通过比较与 $D$ 的大小来判断是否产生“剧烈颠簸”。
• 变量 bad 始终维护当前窗口内不满足条件的相邻对个数。当 bad == 0 时窗口合格，更新最大和。
• 初始窗口需要单独处理，随后在 for 循环中完成 $O(1)$ 的滑动更新。

该解法充分利用了滑动窗口的性质，将检查窗口合法性的复杂度从 $O(W)$ 降为 $O(1)$，从而整体达到 $O(N)$ 的效率。