WA0pts 求调

CEFqwq @ 2023-07-10 15:23:08

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],q[1000005],b[1000005],c[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(register int i=1;i<=n;i++)cin>>a[i];
    memset(q,0,sizeof(q));
    int f=1,e=0;
    q[1]=1;
    for(register int i=1;i<=n;i++){
        while(f<=e&&i-q[f]>k)f++;
        b[i]=a[q[f]];
        while(f<=e&&a[i]<=q[e])e--;
        q[++e]=i;
    }
    memset(q,0,sizeof(q));
    f=1,e=0;
    q[1]=1;
    for(register int i=1;i<=n;i++){
        while(f<=e&&i-q[f]>k)f++;
        c[i]=a[q[f]];
        while(f<=e&&a[i]>=q[e])e--;
        q[++e]=i;
    }
    for(register int i=k;i<=n;i++)cout<<b[i]<<" ";
    cout<<"\n";
    for(register int i=k;i<=n;i++)cout<<c[i]<<" ";
}

by Terrible @ 2023-07-10 15:38:20

@tlxjy 你这个问题有点多啊：

①首先你是在每次加入当前元素之前来查询紧贴着当前元素，前面长度为 k 的区间最值，答案得错一位才是，并且最后的一组区间你没有查。

②a[i]<=q[e] 和 a[i]>=q[e]，单调队列中的值q[i]只用来作下标，必须牢记这一点。所以应该改成 a[i]<=a[q[e]] 和 a[i]>=a[q[e]]。

综上两点，建议你使用先加入当前元素再查询的方式：

    for(int i=1;i<=n;i++){
        while(f<=e&&a[i]<=a[q[e]])e--;
        q[++e]=i;
        while(f<=e&&i-q[f]>=k)f++;
        b[i]=a[q[f]];
    }

这样就对了。

除此之外的枝端末节的东西：

q 数组只需要重置头指针 f 和尾指针 e 即可，我们认为不会调用 [f,e] 之外的元素，也不需要清空数组，况且它开在全局区，初始默认就是 0。两个 memset(q,0,sizeof(q)); 和 两个 q[1]=1; 都可以去掉，这没有意义。

register写到在 C++14 基本没啥意义，编译器：“你在教我做事？”虽然是给编译器建议，但是这个建议真的是没啥用。。。

by CEFqwq @ 2023-07-10 15:59:33

@Terrible 但我这个模板是照着老师打的啊。。。

by CEFqwq @ 2023-07-10 16:02:34

变成了 10pts

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],q[1000005],b[1000005],c[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(register int i=1;i<=n;i++)cin>>a[i];
    memset(q,0,sizeof(q));
    int f=1,e=0;
    q[1]=1;
    for(register int i=1;i<=n;i++){
        while(f<=e&&a[i]<=a[q[e]])e--;
        q[++e]=i;
        while(f<=e&&i-q[f]>=k)f++;
        b[i]=a[q[f]];
    }
    memset(q,0,sizeof(q));
    f=1,e=0;
    q[1]=1;
    for(register int i=1;i<=n;i++){
        while(f<=e&&a[i]>=a[q[e]])e--;
        q[++e]=i;
        while(f<=e&&i-q[f]>k)f++;
        c[i]=a[q[f]];

    }
    for(register int i=k;i<=n;i++)cout<<b[i]<<" ";
    cout<<"\n";
    for(register int i=k;i<=n;i++)cout<<c[i]<<" ";
}

by CEFqwq @ 2023-07-10 16:16:03

A 了 QAQ