0分求助

P1886 滑动窗口 /【模板】单调队列

Qiu_chen @ 2022-11-06 14:13:31

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

int q1[1000005],q2[1000005];

int a[1000005];

int n,k;

int min_deque(){
    int t=1,w=0;
    for(int i=1;i<=n;++i){
        while(t<=w && q1[t]+k<=i)  t++;

        while(t<=w && a[i]<a[q1[w]])  w--;

        q1[++w]=i;

        if(i>=k)  cout<<a[q1[t]];
    }
    cout<<endl;
}
int max_deque(){
    int t=1,w=0;
    for(int i=1;i<=n;++i){
        while(t<=w && q2[t]+k<=i)  t++;

        while(t<=w && a[i]<a[q2[w]])  w--;

        q2[++w]=i;

        if(i>=k)  cout<<a[q2[t]];
    }
    cout<<endl;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i)  cin>>a[i];
    min_deque();
    max_deque();
    return 0;
}

by Adchory @ 2022-11-06 14:35:13

@ricky234

  1. 您没打空格

  2. 您的 min_dequemax_deque 一致

  3. 您的函数名与您函数内容不匹配


|