不明白为什么WA了一个点,求大神

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

forever_shi @ 2017-10-30 16:36:02

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct node
{
    int x,p;
}e[1000001],l[1000001];
int n,m,a[1000001],head=1,tail=1;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    l[1].x=a[1];    
    l[1].p=1;
    for(int i=2;i<=n;i++)
    {
        while(head<=tail&&l[tail].x>=a[i])
        tail--;
        tail++;
        l[tail].x=a[i];
        l[tail].p=i;
        while(l[head].p<i-m+1)
        head++;
        if(i>=m)
        printf("%d ",l[head].x);
    }
    cout<<endl;
    tail=1;
    head=1;
    e[1].x=a[1];
    e[1].p=1;
    for(int i=2;i<=n;i++)
    {
        while(head<=tail&&e[tail].x<=a[i])
        tail--;
        tail++;
        e[tail].x=a[i];
        e[tail].p=i;
        while(e[head].p<i-m+1)
        head++;
        if(i>=m)
        printf("%d ",e[head].x);
    }    
    return 0;
}
//本程序90分,第三个点WA了,测评数据下不来,所以蒟蒻不知所措了

by night @ 2017-11-02 11:41:02

第三个点k=1


by _小妖 @ 2017-11-08 18:47:13

嗯,谢谢楼上,蒟蒻在判断范围的时候加一个head<=tail的条件就好了


|