P1886滑动窗口


单调队列的经典问题,维护两个单调队列,一个递增一个递减

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,k,a[maxn];
int q1[maxn],q2[maxn];
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0') {if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
void workmin()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q1[h]+k<=i) h++;
        while(h<=t&&a[i]<a[q1[t]]) t--;
        q1[++t]=i;
        if(i>=k) printf("%d ",a[q1[h]]);
    }
    printf("\n");
}
void workmax()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&q2[h]+k<=i) h--;
        while(h<=t&&a[i]>a[q2[t]]) t--;
        q2[++t]=i;
        if(i>=k) printf("%d ",a[q2[h]]);
    }
    printf("\n");
}
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    workmin();
    workmax();
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ2689Prime Distance POJ2689Prime Distance
这是区间筛素数的模板,由于l r过大,之间用埃筛一定会超时,由于r-l在接受范围内,所以先把1-根号r的素数预处理一遍,然后再用p*i统计l-r内的素数,注意l=1要特判 #include<cstdio> #include<c
2019-07-05
下一篇 
P2168 NOI2015荷马史诗 P2168 NOI2015荷马史诗
这是k叉哈夫曼树的应用,在构造哈夫曼树的时候,可以用优先队列,这里可以采用pair简化代码,priotity_queue会依次判断大小,一个为当前节点值,另一个为高度,在k叉的时候,有可能会出现到根节点不足k叉的情况,一定不为最优解,所以可
2019-07-05
  目录