很奇怪诶！！！！

zhaoyifan @ 2017-08-16 20:47:07

by zhaoyifan @ 2017-08-16 20:47:30

using namespace std;
int n,k,q[1000007],a[1000007],head=1,tail=0;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        if(q[head]<i-k+1&&head<=tail) head++;
        while(a[q[tail]]>=a[i]&&head<=tail) tail--;
        q[++tail]=i;
        if(i>=k) cout<<a[q[head]]<<" ";
    }
    cout<<endl;head=1,tail=0;
    for(int i=1;i<=n;++i)
    {
        if(q[head]<i-k+1&&head<=tail) head++;
        while(a[q[tail]]<=a[i]&&head<=tail) tail--;
        q[++tail]=i;
        if(i>=k) cout<<a[q[head]]<<" ";
    }
    return 0;
}

by zhaoyifan @ 2017-08-16 20:47:57

using namespace std;
int n,k,q[1000007],a[1000007],head=1,tail=0;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    scanf("%d",&a[i]);
    for(int i=1;i<=k-1;++i)
    {
        if(a[q[tail]]>=a[i]&&head<=tail) tail--;
        q[++tail]=i;
    }
    for(int i=1;i<=n;++i)
    {
        if(q[head]<i&&head<=tail) head++;
        if(i+k-1<=n)
        {
            while(a[q[tail]]>=a[i+k-1]&&head<=tail)tail--;
            q[++tail]=i+k-1;
        }
        if(i<=n-k+1)
        cout<<a[q[head]]<<" ";
    }
    cout<<endl;
    head=1,tail=0;memset(q,0,sizeof(q));
    for(int i=1;i<=k-1;++i)
    {
        if(a[q[tail]]<=a[i]&&head<=tail) tail--;
        q[++tail]=i;
    }
    for(int i=1;i<=n;++i)
    {
        if(q[head]<i&&head<=tail) head++;
        if(i+k-1<=n)
        {
            while(a[q[tail]]<=a[i+k-1]&&head<=tail)tail--;
            q[++tail]=i+k-1;
        }
        if(i<=n-k+1)
        cout<<a[q[head]]<<" ";
    }
}

by vinvor @ 2017-08-16 22:09:37

第一：普通读入优化为WA，需要在主函数开头处加一句“cin.sync_with_stdio(false); ”，然后后面所有读入使用cin，具体此行代码有何作用请自行百度。

第二：内中部分if处应为while，问题在于队列弹出不彻底。

#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
int n,k,q[1000007],a[1000007],head=1,tail=0;
int main()
{
    cin.sync\_with\_stdio(false);  
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=k-1;++i)
    {
        while(a[q[tail]]>=a[i]&&head<=tail) tail--;
        q[++tail]=i;
    }
    for(int i=1;i<=n;++i)
    {
        while(q[head]<i&&head<=tail) head++;
        if(i+k-1<=n)
        {
            while(a[q[tail]]>=a[i+k-1]&&head<=tail)tail--;
            q[++tail]=i+k-1;
        }
        if(i<=n-k+1)
            printf("%d ",a[q[head]]);
    }
    printf("\n");
    head=1,tail=0;memset(q,0,sizeof(q));
    for(int i=1;i<=k-1;++i)
    {
        while(a[q[tail]]<=a[i]&&head<=tail) --tail;
        q[++tail]=i;
    }
    for(int i=1;i<=n;++i)
    {
        while(q[head]<i&&head<=tail) ++head;
        if(i+k-1<=n)
        {
            while(a[q[tail]]<=a[i+k-1]&&head<=tail)--tail;
            q[++tail]=i+k-1;
        }
        if(i<=n-k+1)
            printf("%d ",a[q[head]]);
    }
    return 0;
}
···