单调队列10分WA9个点求教

xingzi @ 2019-07-23 11:00:46

#include<cstdio>
#include<iostream>
using namespace std;
int a[1001000],head=1,tail=1;
struct N{
    int time,v;
}q1[10010000],q2[10010000];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1; i<=n; i++){
        while(a[i]<=q1[tail-1].v&&head<tail){//队尾元素为tail-1 
            tail--;
        }
        q1[tail].time=i;
        q1[tail].v=a[i];
        tail++;
        if(i>=3){
            if(q1[head].time+k<=i)
                head++;
            printf("%d ",q1[head].v);
        }
    }
    printf("\n");
    head=tail=1;
    for(int i=1; i<=n; i++){
        while(a[i]>=q2[tail-1].v&&head<tail)
            tail--;
        q2[tail].time=i;
        q2[tail].v=a[i];
        tail++;
        if(i>=3){
            if(q2[head].time+k<=i)
                head++;
            printf("%d ",q2[head].v);
        } 
    }
    printf("\n");
    return 0;
}

by 有朋自远方来 @ 2019-07-23 11:35:55

给你改了一下：

#include<cstdio>
#include<iostream>

using namespace std;

int n,k,a[1001000],head=1,tail=1;

struct N
{
    int time,v;
}q1[10010000],q2[10010000];

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)  scanf("%d",&a[i]);

    for(int i=1; i<=n; i++)
    {
        while(a[i]<=q1[tail-1].v&&head<tail)  tail--;
        q1[tail].time=i;
        q1[tail].v=a[i];
        tail++;
        if(i>=k)
        {
            while(q1[head].time+k<=i)  head++;
            printf("%d ",q1[head].v);
        }
    }
    printf("\n");

    head=tail=1;
    for(int i=1; i<=n; i++)
    {
        while(a[i]>=q2[tail-1].v&&head<tail)  tail--;
        q2[tail].time=i;
        q2[tail].v=a[i];
        tail++;
        if(i>=k)
        {
            while(q2[head].time+k<=i)  head++;
            printf("%d ",q2[head].v);
        } 
    }
    printf("\n");

    return 0;
}

by 有朋自远方来 @ 2019-07-23 11:37:04

问题是这儿

if(i>=k)
{ while(q1[head].time+k<=i) head++; printf("%d ",q1[head].v); }

by 有朋自远方来 @ 2019-07-23 11:38:28

@xingzi

by xingzi @ 2019-07-23 12:31:19

谢谢，你们太热情了～虽然在看到你的评伦之前解决了问题

by xingzi @ 2019-07-23 12:32:52

@有朋自远方来