[POJ 2823][deque] Sliding Window

原題連結

這道題的時間非常......奇妙。

原本我穩穩的寫完deque想說可以一次水過。

結果竟然T了！？



嗯嗯....換了一個寫法，感覺locality會稍微好點。

結果又T了！？

最後我突發奇想，把language 從G++換成C++
.....
時限是10000MS，終於在7XXXMS過了......

恩.....感覺是stl太慢了......
--------------------------------------------

滑動視窗應該也算是經典算法之一了。

維護一個deque，裡面放的是還有可能成為答案的元素，我們討論如何求一個視窗的最大值。

觀察到，如果一個a[i]>a[j]且i>j，那麼j就是個廢物(?
所以我們可以在i要進入deque的時候把dq尾端所有會變廢物的人踢掉
顯然deque裡面的元素有單調性，所以dq的前端就會是答案

那麼題目所說的視窗長度為k要怎麼維護呢？
很簡單，只要檢查deque的前端元素有沒有超出視窗，有就直接踢掉就好。

#include<cstdio>
#include<cstdlib>
#include<deque>
#include<vector>
using namespace std;
const int maxn=1000000+5;
int a[maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",a+i);
    deque<int> dq;
    for(int i=0;i<n;i++)
    {
        if(dq.size() && dq.front()<=i-k) dq.pop_front();
        while(dq.size() && a[dq.back()]>=a[i]) dq.pop_back();
        dq.push_back(i);
        if(i>=k-1) printf("%d%c",a[dq.front()],i==n-1?'\n':' ');
    }
    dq.clear();
    for(int i=0;i<n;i++)
    {
        if(dq.size() && dq.front()<=i-k) dq.pop_front();
        while(dq.size() && a[dq.back()]<=a[i]) dq.pop_back();
        dq.push_back(i);
        if(i>=k-1) printf("%d%c",a[dq.front()],i==n-1?'\n':' ');
    }
}