20分求助

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

3_甲基吲哚 @ 2019-11-07 18:46:35

单调队列做法,不知道为什么才20分

样例有一个地方跑不过去

样例输出:-1 -3 -3 -3 3 3

3 3 5 5 6 7

这个程序输出:-1 -3 -3 -3 5 3

3 3 5 5 6 7

//单调队列模板 
//写点注释希望半期考后我还记得要点 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int a[MAXN],h=1,t,b[MAXN];//a是双端队列,b也是,共用ht,b存a中元素的序号 
int c[MAXN],d[MAXN];//用来求最大值
int s[MAXN]; 
int main()
{
    int n,k; 
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>s[i];
    for(int i=1;i<=n;i++){//求最小值
        while(s[i]<=a[h]&&h<=t)//有元素且不符合单调就踢掉队尾 
            t--;
        a[++t]=s[i];
        b[t]=i; //这里t就不用++了
        if(b[h]<=i-k)//过时就踢掉 
            h++;
        if(i>=k)//达到窗口了才出解
            cout<<a[h]<<" ";
    }
    cout<<endl;
    h=1;t=0; 
    for(int i=1;i<=n;i++){//复制求最大值
        while(s[i]>=c[h]&&h<=t)
            t--;
        c[++t]=s[i];
        d[t]=i;
        if(d[h]<=i-k)
            h++;
        if(i>=k) 
            cout<<c[h]<<" ";
    } 
    return 0;
 } 

求助


by Victorique_De_Blois @ 2019-11-07 18:54:11

(为什么不用线段树呢


by Lskkkno1 @ 2019-11-07 18:59:08

@真香

应该先踢队头


by 3_甲基吲哚 @ 2019-11-07 19:12:22

@Lskkkno1 可是试了先删队头还是一样呀


by ctq1999 @ 2019-11-07 19:35:09

@真香

同志,是:

while(s[i]<=a[t]&&h<=t)//有元素且不符合单调就踢掉队尾 

s[i] <= a[t] 和队尾比较哦


by ctq1999 @ 2019-11-07 19:35:59

@真香

实测AC了

帮我点个赞呗

https://www.luogu.org/problemnew/solution/P2268


by 3_甲基吲哚 @ 2019-11-08 07:19:14

@ctq1999 十分感谢,已赞


|