?題目鏈接：http://poj.org/problem?id=2823

　題意：

　　一個長度為n的序列上有一個長度為k的滑窗從左向右滑動，問每個時刻滑窗內最小值和最大值。

? 題解：

　　我們考慮單調隊列。

　　對于維護最小值，我們維護一個單調遞增的序列。新加入一個數時，彈出隊尾比他大的數（因為這些數即比他大，又比他靠前，對于后面的區間來說總是不如新加入的數優）。在隊首彈出（在序列中編號<該數在序列中編號-k）的數。然后記錄隊首即該滑窗內最小值。

　　最大值同理維護一個單調遞減的序列即可。

?

#include<iostream> #include<cstdio> #include<cstring> #include<deque> #define LL long long #define RI register int using namespace std; const int INF = 0x7ffffff ; const int N = 1e6 + 10 ;inline int read() {int k = 0 , f = 1 ; char c = getchar() ;for( ; !isdigit(c) ; c = getchar())if(c == '-') f = -1 ;for( ; isdigit(c) ; c = getchar())k = k*10 + c-'0' ;return k*f ; } int n, m ; int a[N], hh[N], gg[N] ; deque<int>q1 ; // 遞減序列維護最大值 deque<int>q2 ; // 遞增序列維護最小值 deque<int>q11 ; // 維護遞增序列的值在數組中的下標 deque<int>q22 ; // 維護遞減序列的值在數組中的下標 int main() {n = read(), m = read() ;for(int i=1;i<=n;i++) a[i] = read() ;for(int i=1;i<m;i++) {while(q1.size() && q1.back() <= a[i]) q1.pop_back(), q11.pop_back() ;while(q2.size() && q2.back() >= a[i]) q2.pop_back(), q22.pop_back() ;q1.push_back(a[i]), q2.push_back(a[i]) ;q11.push_back(i), q22.push_back(i) ;}int cnt = 0 ;for(int i=m;i<=n;i++) {while(q1.size() && q1.back() <= a[i]) q1.pop_back(), q11.pop_back() ;while(q2.size() && q2.back() >= a[i]) q2.pop_back(), q22.pop_back() ;q1.push_back(a[i]), q2.push_back(a[i]) ; q11.push_back(i), q22.push_back(i) ;while(q11.front() <= i-m) q1.pop_front(), q11.pop_front() ;while(q22.front() <= i-m) q2.pop_front(), q22.pop_front() ;hh[++cnt] = q1.front(), gg[cnt] = q2.front() ;}for(int i=1;i<=cnt;i++) printf("%d ",gg[i]) ; printf("\n") ;for(int i=1;i<=cnt;i++) printf("%d ",hh[i]) ;return 0 ; } View Code

?

　update :

　　之前的代碼有些麻煩了，更簡潔的代碼請看這里：

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int N = 1e6 + 10 ; 8 9 inline int read() { 10 int k = 0 , f = 1 ; char c = getchar() ; 11 for( ; !isdigit(c) ; c = getchar()) 12 if(c == '-') f = -1 ; 13 for( ; isdigit(c) ; c = getchar()) 14 k = k*10 + c-'0' ; 15 return k*f ; 16 } 17 int n, m ; 18 int hh[N], q1[N], q2[N], a1[N], a2[N] ; // 單調遞增維護最小值，單調遞減維護最大值 ( 都維護序號 19 20 int main() { 21 n = read(), m = read() ; int h1 = 1, h2 = 1, t1 = 0, t2 = 0 ; 22 for(int i=1;i<=n;i++) hh[i] = read() ; 23 for(int i=1;i<=m;i++) { 24 while(h1 <= t1 && hh[q1[t1]] >= hh[i]) t1-- ; 25 q1[++t1] = i ; 26 while(h2 <= t2 && hh[q2[t2]] <= hh[i]) t2-- ; 27 q2[++t2] = i ; 28 } 29 int tot = 0 ; a1[++tot] = hh[q1[h1]], a2[tot] = hh[q2[h2]] ; 30 for(int i=m+1;i<=n;i++) { 31 while(h1 <= t1 && hh[q1[t1]] >= hh[i]) t1-- ; q1[++t1] = i ; 32 while(q1[h1] <= i-m) h1++ ; 33 while(h2 <= t2 && hh[q2[t2]] <= hh[i]) t2-- ; q2[++t2] = i ; 34 while(q2[h2] <= i-m) h2++ ; 35 a1[++tot] = hh[q1[h1]], a2[tot] = hh[q2[h2]] ; 36 } 37 for(int i=1;i<=tot;i++) printf("%d ",a1[i]) ; printf("\n") ; 38 for(int i=1;i<=tot;i++) printf("%d ",a2[i]) ; 39 return 0 ; 40 }

?

轉載于:https://www.cnblogs.com/zub23333/p/8568040.html

總結

以上是生活随笔為你收集整理的poj2823 Sliding Window的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。