POJ 2823 Sliding Window 单调队列
这道题就是用单调队列来维护，但是用G++交TLE，用c++5000多ms，真是囧...代码很丑，就凑合着看吧 #include<stdio.h> int a[1000009],que[1000009]; int main(){ int n,k,i,head,tail,flag=1,f; scanf("%d %d",&n,&k); for(i=1;i<=n;i++) scanf("%d",&a[i]); head=1;tail=0; f=1; for(i=1;i<=n;i++){ while(tail>=head && a[i]<a[que[tail]]) tail--; que[++tail]=i; if(i>=k){ if(que[head]<f) head++; if(flag){ printf("%d",a[que[head]]); flag=0; } else printf(" %d",a[que[head]]); f++; } } printf("\n"); head=1;tail=0; flag=1; f=1; for(i=1;i<=n;i++){ while(tail>=head && a[i]>a[que[tail]]) tail--; que[++tail]=i; if(i>=k){ if(que[head]<f) head++; if(flag){ printf("%d",a[que[head]]); flag=0; } else printf(" %d",a[que[head]]); f++; } } printf("\n"); }