70分求助

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

黑猫_琉璃 @ 2018-11-03 00:09:22

不好意思深夜打扰了。

这道题我的思路基本是暴力枚举,稍微加了一点点优化。结果提交上去之后发现WA了第2、3、7个点。请问是为什么呢?觉得自己的代码没有问题,可第二个测试点又“该测试点数据过大无法下载”。

求教大佬。

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;

#define INF INT_MAX

int n,k,num[1000005],maxn,minn = INF,cs,maxs[1000005],mins[1000005],len;
bool chgmin = false,chgmax = false;

int main(void){
    //得到数字的数量和滑动窗口的大小
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
    } 
    cs = n - k + 1;
    for(int i=1;i<=k;i++){
        if(num[i] > maxn){
            maxn = num[i];
        }
        if(num[i] < minn){
            minn = num[i];
        }
    }
    //保存
    len++;
    maxs[len] = maxn;
    mins[len] = minn; 
    //判断是否需要更换最小值/最大值 
    if(minn == num[1]){
        chgmin = true;
    } 
    if(maxn == num[1]){
        chgmax = true;
    }
    for(int i=2;i<=cs;i++){
        //得到最大值
        if(!chgmax){
            if(num[i+k-1] > maxn){
                maxn = num[i+k-1];
            }
        }else{
            //重置
            maxn = 0; 
            //遍历之后的k个数
            for(int j=i;j<=k+i-1;j++){
                if(num[j] > maxn){
                    maxn = num[j];
                }
            } 
        }
        //得到最小值
        if(!chgmin){
            if(num[i+k-1] < minn){
                minn = num[i+k-1];
            }
        }else{
            minn = INF;
            for(int j=i;j<=k+i-1;j++){
                if(num[j] < minn){
                    minn = num[j];
                }
            } 
        }
        //保存
        len++;
        maxs[len] = maxn;
        mins[len] = minn; 
        //重置
        chgmax = chgmin = false; 
        //判断是否需要更换最大/最小值
        if(minn == num[i]){
            chgmin = true;
        } 
        if(maxn == num[i]){
            chgmax = true;
        }
    }
    //输出
    for(int i=1;i<=len;i++){
        printf("%d ",mins[i]);
    } 
    printf("\n");
    for(int i=1;i<=len;i++){
        printf("%d ",maxs[i]);
    }
    return 0;
}

by ez_lcw @ 2018-12-05 13:19:37

@黑猫_琉璃 maxn有可能是负数


by 黑猫_琉璃 @ 2018-12-08 11:50:28

@20181gdgzoi236_lc 感谢dalao,我已经AC了。(第一道绿题,想想都有点激动啊)


by ez_lcw @ 2018-12-08 17:57:27

不谢


|