「POI2010」驾驶员 Pilots 题解

题目大意

给定一个整数 $t$ 和一个长度为 $n$ 的序列 $a_1, a_2, ..., a_n$，要求找出最长的连续子串，使得该子串中任意两个元素的差的绝对值不超过 $t$。

解题思路

这个问题可以转化为：寻找最长的连续子数组，使得该子数组中的最大值与最小值之差不超过 $t$。

关键观察

对于任意一个满足条件的子串，其最大值与最小值之差必须 ≤ $t$。因此，我们可以使用**双指针（滑动窗口）**技术，并维护窗口内的最大值和最小值。

算法选择

使用单调队列来维护当前窗口内的最大值和最小值：

• 使用一个单调递减队列维护当前窗口内的最大值
• 使用一个单调递增队列维护当前窗口内的最小值
• 使用双指针维护当前窗口的左右边界

算法流程

1. 初始化左指针 $l = 1$，答案 $ans = 0$
2. 遍历右指针 $r$ 从 1 到 $n$：
   • 维护最大值队列：保证队列单调递减
   • 维护最小值队列：保证队列单调递增
   • 将当前元素加入两个队列
   • 检查当前窗口是否满足条件（最大值 - 最小值 ≤ $t$）
   • 如果不满足，移动左指针直到满足条件
   • 更新答案

时间复杂度

• 每个元素最多入队一次、出队一次
• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

代码实现

#include <bits/stdc++.h>
template <typename T> inline void rd(T &x) {
    x = 0;
    char c = getchar();
    bool f = false;

    for (; !isdigit(c); c = getchar())
        f |= (c == '-');

    for (; isdigit(c); c = getchar())
        x = x * 10 + (c ^ '0');

    if (f)
        x = -x;
}
using namespace std;
const int N = 3e6 + 10;
int k, n, a[N], l = 1, ans;
int mxq[N], mnq[N], mxh = 1, mnh = 1, mxt, mnt;

int main() {
    rd(k), rd(n);

    for (int i = 1; i <= n; ++ i) {
        rd(a[i]);

        // 维护最大值队列（单调递减）
        while (mxh <= mxt and a[mxq[mxt]] < a[i])
            mxt --;

        // 维护最小值队列（单调递增）
        while (mnh <= mnt and a[mnq[mnt]] > a[i])
            mnt --;

        mxq[++ mxt] = mnq[++ mnt] = i;

        // 调整左指针，使窗口满足条件
        while (a[mxq[mxh]] - a[mnq[mnh]] > k) {
            if (mxq[mxh] < mnq[mnh])
                l = mxq[mxh] + 1, mxh ++;
            else
                l = mnq[mnh] + 1, mnh ++;
        }

        ans = max(ans, i - l + 1);
    }

    return printf("%d\n", ans), 0;
}

算法正确性证明

该算法正确性的关键在于：

1. 单调队列维护极值：最大值队列队首始终是当前窗口的最大值，最小值队列队首始终是当前窗口的最小值
2. 双指针有效性：当窗口不满足条件时，移动左指针是必要的，且不会错过最优解
3. 时间复杂度保证：每个元素最多入队出队一次，保证了线性时间复杂度

样例分析

对于样例：

t = 3, n = 9
序列：5 1 3 5 8 6 6 9 10

算法找到的最长子串长度为 4，对应子串 5,8,6,6 或 8,6,6,9，这些子串中任意两数之差都不超过 3。

总结

本题展示了如何结合双指针和单调队列高效解决区间极值约束问题，是滑动窗口类问题的经典应用。