BZOJ_1342_[Baltic2007]Sound静音问题_单调队列

时间：2024-05-06 13:03:19

BZOJ_1342_[Baltic2007]Sound静音问题_单调队列

题意：

给出n个数，求∑[ max{a[i]~a[i+m-1]} - min{a[i]~a[i+m-1]} <= c ]

分析：

滑动窗口

我们维护两个单调队列，分别存最大，最小值

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define N 1000050

#define LL long long

int n, a[N], Q1[N], L1, R1, Q2[N], L2, R2;

int m, c;

int main(){

    scanf("%d%d%d",&n,&m,&c);

    int i, j;

    for(i = 1;i <= n; i++){

        scanf("%d", &a[i]);

    }

    for(i = 1;i <= m; i++){

        while(L1 < R1 && a[i] >= a[Q1[R1 - 1]]) R1--;

        Q1[R1++] = i;

        while(L2 < R2 && a[i] <= a[Q2[R2 - 1]]) R2--;

        Q2[R2++] = i;

    }

    int flg = 0;

    if(a[Q1[L1]] - a[Q2[L2]] <= c) puts("1"),flg=1;

    for(i = 2;i <= n - m + 1; i++){

        while(L1 < R1 && Q1[L1] < i) L1++;

        while(L2 < R2 && Q2[L2] < i) L2++;

        while(L1 < R1 && a[i + m - 1] >= a[Q1[R1 - 1]]) R1--;

        Q1[R1++] = i + m - 1;

        while(L2 < R2 && a[i + m - 1] <= a[Q2[R2 - 1]]) R2--;

        Q2[R2++] = i + m - 1;

        if(a[Q1[L1]] - a[Q2[L2]] <= c) flg = printf("%d\n",i);

    }

    if(! flg) puts("NONE");

}

相关文章