洛谷 P3512. Pilots

问题描述

link

分析

略

参考代码

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

int n, k, ans, a[3000010];

int main() {
    cin >> k >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // q1 单调递减 q2 单调递增
    deque<int> q1, q2;
    int l = 1, r = 1;
    for (; r <= n; r++) {
        while (q1.size() && a[r] > a[q1.back()]) q1.pop_back();
        q1.push_back(r);

        while (q2.size() && a[r] < a[q2.back()]) q2.pop_back();
        q2.push_back(r);

        while (a[q1.front()] - a[q2.front()] > k) {
            ++l;
            while (q1.size() && q1.front() < l) q1.pop_front();
            while (q2.size() && q2.front() < l) q2.pop_front();
        }

        ans = max(ans, r - l + 1);
    }
    cout << ans << endl;

    return 0;
}