求助!70分,WA on 2,3,7

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

Peter20221015 @ 2023-12-08 17:27:15

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(long long i=a;i<=b;i++)
#define per(i,a,b) for(long long i=a;i>=b;i--)
#define N 1000050
#define ll long long

ll n,k,a[N],b[N],Mx,Mn=9999999999,c[N],d[N];

inline ll nmx(ll x,ll u,ll v){
    ll o=0;
    rep(i,u,v){
        if(a[i]>o&&a[i]!=x){
            o=a[i];
        }
    }
    return o;
}

inline ll nmn(ll x,ll u,ll v){
    ll o=9999999999;
    rep(i,u,v){
        if(a[i]<o&&a[i]!=x){
            o=a[i];
        }
    }
    return o;
}

int main(){
    scanf("%lld%lld",&n,&k);
    rep(i,1,n)scanf("%lld",&a[i]);
    rep(i,1,k){
        Mx=max(Mx,a[i]),Mn=min(Mn,a[i]);
        c[1]=Mn,d[1]=Mx;
    }
    rep(i,k+1,n){
        if(a[i-k]==Mx){
            Mx=nmx(Mx,i-k,i-1);
        }
        else if(a[i-k]==Mn){
            Mn=nmn(Mn,i-k,i-1);
        }
        if(a[i]>Mx)Mx=a[i];
        else if(a[i]<Mn)Mn=a[i];
        c[i-k+1]=Mn,d[i-k+1]=Mx;
    }
    rep(i,1,n-k+1)printf("%lld ",c[i]);
    puts("");
    rep(i,1,n-k+1)printf("%lld ",d[i]);
    return 0;
}

虽然有更好的方法,但我想知道这为什么错了。。


by HugeSB @ 2023-12-08 17:39:00

首先这里你的最小值有点问题,要设成﹣无穷大,因为可以在样例里很明显发现这里有负值


by Peter20221015 @ 2023-12-11 16:55:45

@HugeSB 哦,好像是的!


|