POJ2823 Sliding Window(单调队列)

单调队列,我用deque维护。这道题不难写,我第二次写单调队列,1次AC。

-----------------------------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<deque>

#define rep(i,r) for(int i=0;i<r;i++)

#define clr(x,c) memset(x,c,sizeof(x))

#define Rep(i,l,r) for(int i=l;i<r;i++)

using namespace std;

const int maxn=1000000+5;

int n,k;

int Min[maxn],Max[maxn];

deque<int> minq,maxq;

deque<int> minnum,maxnum;

int main()

{

// freopen("test.in","r",stdin);

// freopen("test.out","w",stdout);

while(scanf("%d%d",&n,&k)==2) {

int t;

rep(i,n) {

scanf("%d",&t);

if(minq.empty()) {

minq.push_back(t); minnum.push_back(i);

} else {

while(!minq.empty() && minnum.front()<=i-k) {

minq.pop_front();

minnum.pop_front();

}

while(!minq.empty() && minq.back()>=t) {

minq.pop_back();

minnum.pop_back();

}

minq.push_back(t); minnum.push_back(i);

}

if(maxq.empty()) {

maxq.push_back(t); maxnum.push_back(i);

} else {

while(!maxq.empty() && maxnum.front()<=i-k) {

maxq.pop_front();

maxnum.pop_front();

}

while(!maxq.empty() && maxq.back()<=t) {

maxq.pop_back();

maxnum.pop_back();

}

maxq.push_back(t); maxnum.push_back(i);

}

Min[i]=minq.front(); Max[i]=maxq.front();

}

Rep(i,k-1,n) printf("%d ",Min[i]);

printf("\n");

Rep(i,k-1,n) printf("%d ",Max[i]);

printf("\n");

}

return 0;

}

-----------------------------------------------------------------------------------

Sliding Window

Time Limit: 12000MS Memory Limit: 65536K
Total Submissions: 41760 Accepted: 12360
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

8 3 1 3 -1 -3 5 3 6 7 

Sample Output

-1 -3 -3 -3 3 3 3 3 5 5 6 7 

Source

POJ Monthly--2006.04.28, Ikki

时间: 03-18

POJ2823 Sliding Window(单调队列)的相关文章

POJ2823 Sliding Window (单调队列的基本应用)

题目链接: http://poj.org/problem?id=2823 题意: 给定一个长度为n的序列,求每个长度为k的区间的最大值与最小值 分析: 单调队列的基本应用 代码如下: <span style="font-size:14px;">#include <iostream> #include <cstring> #include <cstdio> #include <queue> #include <vector

POJ2823.Sliding Window——单调队列

http://poj.org/problem?id=2823 求长度为k的子序列里面的最大值,最小值 #include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <algorithm> #define pk push_back const int INF = 0x3f3f3f3f; const int maxn = 1000010; usi

POJ 2823 Sliding Window 单调队列题解

本题是单调队列题解的入门,当然也可以使用RMQ 和 线段树,不过速度都没有单调队列那么快. 单调队列难点: 1 如何入列,保存数据 -- 最小单调队列的时候, 所有数都入列一次,在新的数据准备入列的时候,增加判断,如果当前数值小于队尾数值,那么队尾数值就出列.空队列的时候直接入列. 2 保存的数列是什么样的? 举例吧: 1 3 -1 -3 5 3 6 7 构建最小单调队列 第一个数值1的时候,空队列,那么入列,得到: 1 第二个数值3, 因为大于1:那么1不用出列,直接入列,得到: 1 3 第三

poj 2823 Sliding Window 单调队列或线段树

题目链接:http://poj.org/problem?id=2823 Sliding Window Time Limit: 12000MS   Memory Limit: 65536K Total Submissions: 38315   Accepted: 11350 Case Time Limit: 5000MS Description An array of size n ≤ 106 is given to you. There is a sliding window of size k

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

poj 2823 Sliding Window (单调队列入门)

1 /***************************************************************** 2 题目: Sliding Window(poj 2823) 3 链接: http://poj.org/problem?id=2823 4 题意: 给一个数列,找所有连续k个数的最小值和最大值. 5 算法: 单调队列(入门) 6 ******************************************************************

POJ2823 Sliding Window (单调队列)

POJ2823 Sliding Window Time Limit: 12000MS   Memory Limit: 65536K Total Submissions: 38342   Accepted: 11359 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 ve

POJ2823 Sliding Window【双端队列】

求连续的k个中最大最小值,k是滑动的,每次滑动一个 用双端队列维护可能的答案值 如果要求最小值,则维护一个单调递增的序列 对一开始的前k个,新加入的如果比队尾的小,则弹出队尾的,直到新加入的比队尾大,加入队尾 从第k+1个到最后一个,按照上述规则,压入新数,然后弹出队首元素(满足队首元素对应原来序列的位置必须在视窗内,否则,继续弹出下一个) #include <cstdio> #include <cstdlib> #include <iostream> #include

POJ2823 Sliding Window

Time Limit: 12000MS   Memory Limit: 65536K Total Submissions: 53086   Accepted: 15227 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