POJ 2823 Sliding Window

POJ 2823 Sliding Window

題目概述:

給一個n個數的數列，求連續的每k個數(1~k , 2~k+1 , 3~k+2 ,,,,, n-k+1~n ) 的最大和最小值。

思路:

這題時間卡超緊。。。本來想說直接用multiset (O(nlogn))就可以輕鬆過(註解掉的地方)，結果TLE。

後來改用單調隊列(O(n))，用deque來實作，結果還是TLE= = 不知道是不是哪裡沒優化好

後來再用陣列自己實作deque才過。

AC code:

//By SCJ

//POJ 2823

#include<cstdio>

#include<set>

#include<deque>

using namespace std;

#define endl '\n'

#define maxn 1000000

int a[maxn],mia[maxn],maa[maxn],mi_back=-1,ma_back=-1,mi_front=0,ma_front=0;

pair<int,int> mi[maxn],ma[maxn];

int main()

{

int n,k;scanf("%d%d",&n,&k);

for(int i=0;i<n;++i) scanf("%d",&a[i]);

for(int i=0;i<n;++i)

{

while( mi_back>=mi_front &&a[i]<mi[mi_back].first) mi_back--;

mi[++mi_back]=(make_pair(a[i],i));

while( ma_back>=ma_front &&a[i]>ma[ma_back].first) ma_back--;

ma[++ma_back]=(make_pair(a[i],i));

if(i>=k-1)

{

while(mi[mi_front].second<i-k+1) mi_front++;

while(ma[ma_front].second<i-k+1) ma_front++;

mia[i]=mi[mi_front].first;maa[i]=ma[ma_front].first;

}

}

for(int i=k-1;i<n;++i) printf("%d ",mia[i]);

puts("");

for(int i=k-1;i<n;++i) printf("%d ",maa[i]);

puts("");

/*

int n,k,tp;scanf("%d%d",&n,&k);

multiset<int> s;

for(int i=0;i<n;++i) scanf("%d",&a[i]);

for(int i=0;i<k;++i) s.insert(a[i]);

mi[k-1]=*s.begin();ma[k-1]=*(--s.end());

for(int i=k;i<n;++i)

{

s.erase(s.find(a[i-k]));

s.insert(a[i]);

mi[i]=*s.begin();ma[i]=*(--(s.end()));

}

for(int i=k-1;i<n;++i) printf("%d ",mi[i]);

puts("");

for(int i=k-1;i<n;++i) printf("%d ",ma[i]);

*/

}