[bzoj2096]: [Poi2010]Pilots

[bzoj2096]: [Poi2010]Pilots

题目链接

力量本身并不可怕,可怕的是它的主人

Solution

因为n很大,必须要线性的做法。

我们考虑如果右端点向右移动的话,左端点一定是单调不下降的。

那么维护一个单调队列,维护区间最大值和最小值即可,每次删除的时候判断一下。

Code

#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    do {x = x * 10 + (c ^ 48); c = getchar();} while(isdigit(c));
    return x * f;
}

const int N = 3e6 + 29;
deque<int> q1, q2;
int a[N];

int main() {
    int k = read(), n = read(), ans = 0, t = 1;
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i) {
        while(!q1.empty() && a[q1.back()] > a[i]) q1.pop_back();
        while(!q2.empty() && a[q2.back()] < a[i]) q2.pop_back();
        q1.push_back(i); q2.push_back(i);
        while(a[q2.front()] - a[q1.front()] > k) 
            if(q1.front() < q2.front()) {
                t = q1.front() + 1;
                q1.pop_front();
            } else {
                t = q2.front() + 1;
                q2.pop_front();
            }
        ans = max(ans, i - t + 1);
       // printf("%d\n", ans);
    }
    printf("%d\n", ans);
    return 0;
}

/*
3 9
5 1 3 5 8 6 6 9 10
*/

说点什么

avatar
  Subscribe  
提醒