暴力枚举70分求助

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

happyzy226 @ 2018-10-27 22:24:51

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

int n,k,a[1000005],maxn[1000005],minn[1000005];

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    memset(minn,INT_MAX,sizeof(minn));
    for(int i=1;i<=k;i++)
    {
        minn[1]=min(minn[1],a[i]);
        maxn[1]=max(maxn[1],a[i]);
    }
    for(int i=2;i<=n-k+1;i++)
    {
        if(minn[i-1]==a[i-1])
        {
            minn[i]=INT_MAX;
            for(int j=i;j<=i+k-1;j++)
            {
                minn[i]=min(minn[i],a[j]);
            }
        }
        else 
            minn[i]=min(minn[i-1],a[i+k-1]);
        if(maxn[i-1]==a[i-1])
        {
            maxn[i]=0;
            for(int j=i;j<=i+k-1;j++)
            {
                maxn[i]=max(maxn[i],a[j]);
            }
        }
        else 
            maxn[i]=max(maxn[i-1],a[i+k-1]);
    }
    for(int i=1;i<=n-k+1;i++)
        cout<<minn[i]<<' ';
    cout<<"\n";
    for(int i=1;i<=n-k+1;i++)
        cout<<maxn[i]<<' ';
    return 0;
}

by happyzy226 @ 2018-10-27 22:28:36

2,3,7个点WA


by SocietyNiu @ 2018-10-27 22:56:20

真-暴力


by happyzy226 @ 2018-10-28 00:01:01

但是哪里有错啊


by ez_lcw @ 2018-12-05 13:20:58

@happyzy226 maxn有可能为负数,所以maxn初始化时要为负数


by ez_lcw @ 2018-12-05 13:21:18

-INF


|