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

利用單調(diào)隊(duì)列的出隊(duì)入隊(duì)，維護(hù)區(qū)間的最值，保證隊(duì)列單調(diào)遞增或單調(diào)遞減，要維護(hù)單調(diào)遞增隊(duì)列，當(dāng)一個數(shù)字插入的時候，從隊(duì)尾往前找到第一個比它小的值把后面的值都刪掉，然后把這個值放在找到的位置的后面，單調(diào)遞減隊(duì)列也是類似的情況，因?yàn)槭菃握{(diào)序列，查找過程可以用二分查找。

View Code 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define N 1000005 5 using namespace std; 6 int val[N],Min[N],Max[N]; 7 int id[N]; 8 int dmin(int f,int r,int d) 9 { 10 int mid; 11 while(f<=r) 12 { 13 mid=(f+r)>>1; 14 if(Min[mid]==d) 15 return mid; 16 if(Min[mid]>d) 17 r=mid-1; 18 else 19 f=mid+1; 20 } 21 return f; 22 } 23 int dmax(int f,int r,int d) 24 { 25 int mid; 26 while(f<=r) 27 { 28 mid=(f+r)>>1; 29 if(Max[mid]==d) 30 return mid; 31 if(Max[mid]<d) 32 r=mid-1; 33 else 34 f=mid+1; 35 } 36 return f; 37 } 38 int main() 39 { 40 int f1,f2,r1,r2,n,k,i,j; 41 scanf("%d%d",&n,&k); 42 for(i=1;i<=n;i++) 43 scanf("%d",&val[i]); 44 if(k==1)//本以為加上能快一些，沒想到還不如不加 45 { 46 for(i=1;i<=n;i++) 47 { 48 if(i!=1) 49 printf(" "); 50 printf("%d",val[i]); 51 } 52 printf("\n"); 53 for(i=1;i<=n;i++) 54 { 55 if(i!=1) 56 printf(" "); 57 printf("%d",val[i]); 58 } 59 printf("\n"); 60 return 0; 61 } 62 f1=r1=1; 63 Min[1]=val[1]; 64 id[1]=1; 65 for(i=2;i<=k;i++) 66 { 67 r1=dmin(f1,r1,val[i]); 68 //printf("%d\n",Min[1]); 69 Min[r1]=val[i]; 70 id[r1]=i; 71 } 72 printf("%d",Min[1]); 73 for(i=k+1;i<=n;i++) 74 { 75 r1=dmin(f1,r1,val[i]); 76 Min[r1]=val[i]; 77 id[r1]=i; 78 while(i-id[f1]>=k) 79 f1++; 80 printf(" %d",Min[f1]); 81 } 82 printf("\n"); 83 f2=r2=1; 84 Max[1]=val[1]; 85 id[1]=1; 86 for(i=2;i<=k;i++) 87 { 88 r2=dmax(f2,r2,val[i]); 89 Max[r2]=val[i]; 90 id[r2]=i; 91 } 92 printf("%d",Max[1]); 93 for(i=k+1;i<=n;i++) 94 { 95 r2=dmax(f2,r2,val[i]); 96 Max[r2]=val[i]; 97 id[r2]=i; 98 while(i-id[f2]>=k) 99 f2++; 100 printf(" %d",Max[f2]); 101 } 102 printf("\n"); 103 return 0; 104 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/caozhenhai/archive/2012/08/28/2660072.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2823-Sliding Window单调队列解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。