hdu 3415 Max Sum of Max-K-sub-sequence (单调队列)

hdu 3415
题意:给出n个整数,是一个环(也就是a[n]右边是a[1])求一段长度不超过k的数使得和最大,问最大和是多少并给出这段数的位置。

思路:为了处理环,先把n个数复制一下就好,然后求前缀和sum[i]

由于区间[l,r]的和可以用前缀和表示为sum[r]-sum[l-1]

因此在区间长度小于等于k的前提下,我要求sum[r]-sum[l-1]的最大值,如果我们考虑把端点r固定,那么就是要求[l-1,r-1]中的sum的最小值。

因此我们考虑用单调队列来维护sum[i-k]到sum[i-1]的最小值。

我们的做法是:枚举区间右端点i,同时用单调队列维护i之前的k个数[i-k,i-1]的最小值。

由于要求“If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.”,因此从后面出队的判断条件是严格的sum[dq.back()]>sum[i-1]

 

 

 

 

ural 1126. Magnetic Storms (单调队列模板题)

ural 1126
题意:n个数,求从第k个元素开始,求每k个元素的最大值(一共求n-k+1次)
思路:单调队列。
单调队列学习链接
其实单调队列挺容易的理解的。。。当时觉得写不明白大概是因为看到的代码写得太丑了2333

说下我的理解:

单调队列的尾端(就是后进入元素的那一端)其实和单调栈类似。

首端加了个元素期限的概念,不断删除“过期”的元素。

所谓过期的元素,对于这道题来说,当我往前移动到第k+1个元素的时候,第1个元素就是过期了的元素,堆答案不会再有贡献。

理论上单调队列中的元素是<元素的期限,元素>的二元组。

而一般元素的”期限”是由下标的位置决定的,而得到下标就可以知道元素。

所以我们实际操作的时候只需要将下标存入单调队列中就行了。

那么查询最大值呢? 队首元素就是最大值。

以及,用到了stl的双端队列deque(double end queue),头文件是#include <deque>

由于每次的答案是队首元素,因此设置哨兵而使得队列不为空就使得问题变得繁琐。

所以这里不同于单调栈的写法,我们不设置哨兵,而是.empty()判断双端队列是否为空。

也正是因为这个原因,没有办法像单调栈一样写成for的样子(因为没有哨兵,初始x=dq.front()的时候可能dp中还没有元素,导致RE),而是写成while的样子。。具体见代码。

 

 

 

 

poj 2823 Sliding Window (单调队列)

Sliding Window
Time Limit: 12000MS Memory Limit: 65536K
Total Submissions: 46705 Accepted: 13485
Case Time Limit: 5000MS

Description

An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position Minimum value Maximum value
[1  3  -1] -3  5  3  6  7  -1 3
 1 [3  -1  -3] 5  3  6  7  -3 3
 1  3 [-1  -3  5] 3  6  7  -3 5
 1  3  -1 [-3  5  3] 6  7  -3 5
 1  3  -1  -3 [5  3  6] 7  3 6
 1  3  -1  -3  5 [3  6  7] 3 7

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Sample Input

Sample Output

Source

关于单调队列的讲解:

看这个问题:An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position.Your task is to determine the maximum and minimum values in the sliding window at each position.

也就是有一个数列a,要求你求数列b和c,b[i]是a[i]…a[i+w-1]中的最小值,c[i]是最大值。如果a是1,3,-1,-3,5,3,6,7,则b为-1,-3,-3,-3,3,3,c为3,3,5,5,6,7。

这个问题相当于一个数据流(数列a)在不断地到来,而数据是不断过期的,相当于我们只能保存有限的数据(sliding window中的数据,此题中就是窗口的宽度w),对于到来的查询(此题中查询是每时刻都有的),我们要返回当前滑动窗口中的最大值最小值。注意,元素是不断过期的。

解决这个问题可以使用一种叫做单调队列的数据结构,它维护这样一种队列:

a)从队头到队尾,元素在我们所关注的指标下是递减的(严格递减,而不是非递增),比如查询如果每次问的是窗口内的最小值,那么队列中元素从左至右就应该递增,如果每次问的是窗口内的最大值,则应该递减,依此类推。这是为了保证每次查询只需要取队头元素。

b)从队头到队尾,元素对应的时刻(此题中是该元素在数列a中的下标)是递增的,但不要求连续,这是为了保证最左面的元素总是最先过期,且每当有新元素来临的时候一定是插入队尾。

满足以上两点的队列就是单调队列,首先,只有第一个元素的序列一定是单调队列。

那么怎么维护这个单调队列呢?无非是处理插入和查询两个操作。

对于插入,由于性质b,因此来的新元素插入到队列的最后就能维持b)继续成立。但是为了维护a)的成立,即元素在我们关注的指标下递减,从队尾插入新元素的时候可能要删除队尾的一些元素,具体说来就是,找到第一个大于(在所关注指标下)新元素的元素,删除其后所有元素,并将新元素插于其后。因为所有被删除的元素都比新元素要小,而且比新元素要旧,因此在以后的任何查询中都不可能成为答案,所以可以放心删除。

对于查询,由于性质b,因此所有该时刻过期的元素一定都集中在队头,因此利用查询的时机删除队头所有过期的元素,在不含过期元素后,队头得元素就是查询的答案(性质a),将其返回即可。

由于每个元素都进队出队一次,因此摊销复杂度为O(n)。

POJ2823就是上面描述的那道题。

http://www.cnblogs.com/Jason-Damon/archive/2012/04/19/2457889.html

讲得很好.我认为重点的地方加颜色了.

如果要找最大值,那么比新加入的元素小且旧的元素是不可能成为答案的,可以放心删去!

理解了这句话就理解了单调队列…

上面那个博客将得是挺好,只是代码写得略丑.

自己按照思想写了个还看得过去的

更新一个双端队列实现的(为毛交g++会Tle,交c++才能过2333):