POJ 2823 Sliding Window 单调队列题解

2020-12-13 04:10

阅读：530

标签：使用数据 for io window amp

本题是单调队列题解的入门，当然也可以使用RMQ 和线段树，不过速度都没有单调队列那么快。

单调队列难点：

1 如何入列，保存数据 -- 最小单调队列的时候，所有数都入列一次，在新的数据准备入列的时候，增加判断，如果当前数值小于队尾数值，那么队尾数值就出列。空队列的时候直接入列。

2 保存的数列是什么样的？

举例吧： 1 3 -1 -3 5 3 6 7

构建最小单调队列

第一个数值1的时候，空队列，那么入列，得到： 1

第二个数值3，因为大于1；那么1不用出列，直接入列，得到： 1 3

第三个数值-1，因为小于3，故此3出列，-1入列，继续判断-1小于1，故此1也出列，剩下队列得到： -1

以此类推……

根据实际情况，本题需要的是K大小端中的最小和最大值，那么就可以记录上各个数值的下标，加以判断。即下标不在需要的判断范围之内的就出来，不过这次是从队列头出列。因为去掉这些下标不合要求的数值之后，队列的头数值依然是最小值，故此是当前答案。

#include
const int MAX_N = 1000001;

int N, K;
int arr[MAX_N];
int qu[MAX_N];
int index[MAX_N];
int ans[MAX_N];

void getMins()
{
	int tail = 0, head = 1;	//初始化tail= head && qu[tail] >= arr[i]) tail--;
		qu[++tail] = arr[i];		//记录可能的答案值
		index[tail] = i;	//记录额外需要判断的信息
	}
	for (int i = K; i = head && qu[tail] >= arr[i]) tail--; //不符合条件出列
		qu[++tail] = arr[i];
		index[tail] = i;
		while (index[head] = head && qu[tail] = head && qu[tail] 

POJ 2823 Sliding Window 单调队列题解,搜素材,soscw.com
POJ 2823 Sliding Window 单调队列题解
标签：使用   数据   for   io   window   amp   
原文地址：http://blog.csdn.net/kenden23/article/details/37598147

上一篇：多线性方程组迭代算法——Gauss-Seidel迭代算法的Python实现

下一篇：Java 数学操作类

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：POJ 2823 Sliding Window 单调队列题解
文章链接：http://soscw.com/essay/29086.html

亲，登录后才可以留言！

POJ 2823 Sliding Window 单调队列题解

评论

热门文章

推荐文章

最新文章

置顶文章