ACM-单调队列之Sliding Window——poj2823

2020-11-18 19:50

阅读：722

1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长队首。
2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止
要特别注意头指针和尾指针的应用。


参考资料：http://www.cnblogs.com/neverforget/archive/2011/10/13/ll.html
        http://xuyemin520.is-programmer.com/posts/25964
And 这道题就可以解决了。


/**************************************
***************************************
*        Author:Tree                  *
*From :http://blog.csdn.net/lttree    *
* Title : Sliding Window              *
*Source: poj 2823                     *
* Hint  : 单调队列                   *
***************************************
**************************************/
#include 
#define MAX 1000001
int n,k;
int pre1,pre2,lst1,lst2,len_max,len_min;    // 两个队列的头指针与尾指针,最大值的下标，最小值的下表
int num[MAX],Increase[MAX],Decrease[MAX],Max[MAX],Min[MAX];      // Num存数据，递增与递减队列，最大值，最小值的数组。
// 递增序列的压入操作
void in_max(int i)
{
    while( pre1=k )
    {
        if(Increase[pre1]num[i] )
        --lst2;
    Decrease[++lst2]=i;

    // 如果大于等于k个数，就需要向最小值数组赋值
    if( i>=k )
    {
        if(Decrease[pre2]

上一篇：删除windows服务 cygwin sshd

下一篇：Windows server 2003域控直接迁移到2012[史上最详细]

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：ACM-单调队列之Sliding Window——poj2823
文章链接：http://soscw.com/index.php/essay/21908.html

亲，登录后才可以留言！

ACM-单调队列之Sliding Window——poj2823

评论

热门文章

推荐文章

最新文章

置顶文章