90分求助 #1测试点错了

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

天宇1105 @ 2020-10-13 13:57:02

#include <bits/stdc++.h>
using namespace std;
int n,k,q[1000001],e[1000001];
int head=0,tail=0;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    q[head]=0;
    for (int i = 0; i < n; ++i)
    {
        cin>>e[i];
    }
    if(k==1)
    for (int i = 0; i < n; ++i)
    {
        cout<<e[i]<<" ";
    }
    else
    for (int i = 0; i < n; ++i)
    {
        if (i-q[head]>=k)
        {
            head++;
        }
        while((head<=tail)&&(e[q[tail]]>e[i])) tail--;
        tail++;
        q[tail]=i;
        if(i>=k-1)cout<<e[q[head]]<<" ";
    }
    cout<<endl;
    head=0,tail=0;
    if(k==1)
    for (int i = 0; i < n; ++i)
    {
        cout<<e[i]<<" ";
    }
    else
    for (int i = 0; i < n; ++i)
    {
        if (i-q[head]>=k)
        {
            head++;
        }
        while((head<=tail)&&(e[q[tail]]<e[i])) tail--;
        tail++;
        q[tail]=i;
        if(i>=k-1)cout<<e[q[head]]<<" ";
    }
    return 0;
}

by wsyhb @ 2020-10-13 16:36:03

@天宇1105

手工队列中一开始有元素 0,而这份代码每次只使用 if 删除滑出窗口的 1 个元素,那么很有可能出现恰好在窗口之外的元素在队列中没有被删除,即可能窗口长度为 k+1

给一组 Hack 数据(本人手造):

Input
5 3
1 2 3 4 5

Output
1 2 3
3 4 5

/*
代码输出
1 1 2
3 4 5
*/

解决方法有两种:

  1. 一开始队列里不要有元素,即 head=1,tail=0

代码(评测记录)

  1. 每次使用 while 删除元素

代码(评测记录)

话说这竟然能得 90 分


by 天宇1105 @ 2020-10-13 18:08:35

谢谢了


|