哪里的边界判定有问题吗?为什么过不了M==1的点?

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

huangwux @ 2019-10-25 22:56:15

#include<iostream>
#include<string>
#include<queue>
#include<cstdio>
#include<string.h>
using namespace std;
int n,m;
int a[1000100];
int maxx[1000010],minx[1000010];
int now_max,now_min;
int q_max[1000010],q_min[1000010];
int main(){
    //freopen("4.in","r",stdin);
    memset(maxx,-0x3f3f3f3f,sizeof(maxx));
    memset(minx,0x3f3f3f3f,sizeof(minx));
    //q_max[1]=-0x3f,q_min[1]=0x3f;
    scanf("%d%d",&n,&m);
    //int k=m;
    //cout<<n<<"  "<<m<<endl;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]),maxx[i]=minx[i]=a[i];
    /*for(int i=1;i<=n;i++)
    printf("%d %d\n",maxx[i],minx[i]);
    for(int i=1;i<=m;i++)
    {
    if(a[i]>=maxx[m])
    maxx[m]=a[i],q_max[1]=i;
    if(a[i]<=minx[m])
    minx[m]=a[i],q_min[1]=i;
    }
    printf("%d %d %d %d\n",maxx[m],minx[m],q_max[1],q_min[1]);*/
    //maxx[m]=q_max[1],minx[m]=q_min[1];
    int l1=1,r1=1,l2=1,r2=1;
    q_max[1]=q_min[1]=1;
    for(int i=1;i<=n;i++){
        while(l1<=r1&&i-q_max[l1]>=m) l1++;
        maxx[i]=max(maxx[i],a[q_max[l1]]);
        //printf("%d ",maxx[i]);
        while(l1<=r1&&a[q_max[r1]]<=a[i]) r1--;
        q_max[++r1]=i;
        while(l2<=r2&&i-q_min[l2]>=m) l2++;
        minx[i]=min(minx[i],a[q_min[l2]]);
        while(l2<=r2&&a[q_min[r2]]>=a[i]) r2--;
        q_min[++r2]=i;
    }
    for(int i=m;i<=n;i++)
    {
    printf("%d ",minx[i]);
    }
    puts(" ");
    for(int i=m;i<=n;i++)
    {
    printf("%d ",maxx[i]);
    }
}

by 梧桐灯 @ 2019-10-25 22:59:03

哪有这样memset的……


by nth_element @ 2019-10-25 23:09:25

memset(maxx,-0x3f3f3f3f,sizeof(maxx));这时maxx[]是正数


by nth_element @ 2019-10-25 23:09:31

@huangwux


|