POJ2823 Sliding Window 单调队列维护

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

经典的单调队列维护。

单调队列可以在O(n)的时间内完成当前查找区间的最大值最小值的维护。

具体实现:

使用双端队列方便元素进出。元素保存的不是数而是数的位置,因为此题涉及到不在区间内的元素的删除,所以我们应该保存书的位置。

两个单调队列都要在遍历时,都要弹出当前不在查找区间内的元素。我们可以保证,如果要弹出,那么这个元素一定在队列的最开头。

第一个单调队列维护区间最小值,如果当前位置上的数比单调队列中的最后一个元素位置上的数大,则删除单调队列末尾位置的元素,一直到队列为空或者队列末尾元素位置的数比当前位置的数小,然后将当前位置编号加入队列。

第二个单调队列维护区间最大值,类比第一个单调队列。

记得循环的时候就保存答案。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e6+5;
int n,k;
int a[maxn];
dequeq1;
dequeq2;
int ans1[maxn];
int ans2[maxn];
int main(){
    n = get_num();
    k = get_num();
    for(int i = 1;i <= n;++i){
        a[i] = get_num();
    }
    for(int i = 1;i <= n;++i){
        if(!q1.empty() && q1.front() + k <= i)
            q1.pop_front();
        if(!q2.empty() && q2.front() + k <= i)
            q2.pop_front();
        while(!q1.empty() && a[q1.back()] < a[i]){
            q1.pop_back();
        }
        q1.push_back(i);
        while(!q2.empty() && a[q2.back()] > a[i]){
            q2.pop_back();
        }
        q2.push_back(i);
        if(i >= k){
            ans1[i-k+1] = a[q2.front()];
            ans2[i-k+1] = a[q1.front()];
        }
    }
    for(int i = k;i <= n;++i){
        printf("%d ",ans1[i-k+1]);
    }
    printf("\n");
    for(int i = k;i <= n;++i){
        printf("%d ",ans2[i-k+1]);
    }
    printf("\n");
    return 0;
} 

 

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00