POJ2823-Sliding Window

2021-04-14 05:25

阅读：392

标签：存在 code clu 出现 algorithm amp AC 区间不用

给定两个数n和k，接下来给出n个数的数列。每次维护一个长度为k的窗口，求出这个范围的最大值和最小值。每次向右移动一个单位。

考虑如何得出一个区间的最大值，每次增加一个数，如果这个数比当前的最大值小，如何是可以不用维护的。如果比当前值大，那么就要考虑。但是当这个最大值在最左边的时候，它下一次就不能在这个区间了。所以我们要维护的是一个值可以存在的最左的位置。即位置i的生存期最多是i+k，但如果中间出现比它大的数，那么就没必要维护这个数了，可以用出现的数代替它。因为它总是比维护当前的数更优，无论是数值上还是位置上。

也就是说，我们要维护一个递减的数列，可以用单调队列实现做到O(n)的复杂度。

最小值同理，代码如下：

#include 
#include 
#include string.h>
#include 
#include 
using namespace std;

int n,k,v[2333333],q[23333333];
int main() {
    while(~scanf("%d%d",&n,&k)){
        for(int i=1;ii)
            scanf("%d",&v[i]);
        
        int l=1,r=1;
        q[1]=0;
        v[0]=1e9;
        for(int i=1;i1;++i){
            while(li)
                ++l;
            if(ik)
                ;
            else printf("%d ",v[q[l]]);
            while(l=v[i])
                --r;
            q[++r]=i;
        }
        puts("");
        //printf("%d\n",v[q[l]]);
        l=1,r=1;
        q[1]=0;
        v[0]=-1e9;
        for(int i=1;i1;++i){
            while(li)
                ++l;
            /*
            for(int j=l;j*/
            if(ik)
                ;
            else 
                printf("%d ",v[q[l]]);
            while(lv[i])
                --r;
            q[++r]=i;
        }
        puts("");
        //printf("%d\n",v[q[l]]);
    }
    return 0;
}

POJ2823-Sliding Window

标签：存在 code clu 出现 algorithm amp AC 区间不用

原文地址：https://www.cnblogs.com/-Chamgin/p/8969395.html

上一篇：PHPexcel导出

下一篇：windows 游戏编程大师读书笔记

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：POJ2823-Sliding Window
文章链接：http://soscw.com/index.php/essay/75514.html

亲，登录后才可以留言！

POJ2823-Sliding Window

评论

热门文章

推荐文章

最新文章

置顶文章