NKOJ2152 滑动窗口 时间限制 : 10000 MS 空间限制 : 65536 KB
问题描述 给你一个长度为N(N<=10^6)的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，找出窗体所包含的数字的最大和最小值，如下表所示：k的值为3
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7
输入格式 第1行为n，k，第2行为长度为n的数组。
输出格式 共2行，第1行是每个位置的min value，第2行是每个位置的max value。
样例输入 8 3 1 3 -1 -3 5 3 6 7
样例输出 -1 -3 -3 -3 3 3 3 3 5 5 6 7
来源 poj 2823
思路： 求max，维护单调递减队列，如果top>当前值，pop，然后push当前值。再pop_back在讨论区间外的元素，最后的back即为所求。
//结构体加STL #include<cstdio> #include<deque> using namespace std; const int need=1000004; struct fy{int id,u;}a; int ans1[need],ans2[need]; deque<fy>z,j; inline void in_(int &d) { bool mark=false;char t=getchar(); while(t<'0'||t>'9'){if(t=='-') mark=true;t=getchar();} for(d=0;t>='0'&&t<='9';t=getchar())d=(d<<3)+(d<<1)-'0'+t; if(mark) d=-d; } char o[100]; inline void out_(int x) { int l=1; if(x<0) x=-x,putchar('-'); if(!x) putchar('0'); for(;x;x/=10) o[l++]=x%10+'0'; for(l--;l;l--)putchar(o[l]); putchar(' '); } int main() { int n,k;scanf("%d%d",&n,&k); for(int i=1;i<k;i++) { in_(a.u);//scanf("%d",&a.u); a.id=i; while(z.size()>0&&z.back().u>=a.u) z.pop_back(); z.push_back(a); while(j.size()>0&&j.back().u<=a.u) j.pop_back(); j.push_back(a); } for(int i=1;i<=n-k+1;i++) { in_(a.u);//scanf("%d",&a.u); a.id=i+k-1; while(z.size()>0&&z.back().u>=a.u) z.pop_back(); z.push_back(a); while(j.size()>0&&j.back().u<=a.u) j.pop_back(); j.push_back(a); while(z.size()>0&&z.front().id<i) z.pop_front(); while(j.size()>0&&j.front().id<i) j.pop_front(); ans1[i]=z.front().u; ans2[i]=j.front().u; } for(int i=1;i<=n-k+1;i++) out_(ans1[i]);//printf("%d ",ans1[i]); puts(""); for(int i=1;i<=n-k+1;i++) out_(ans2[i]);//printf("%d ",ans2[i]); } //手工&没用结构体 #include<cstdio> #include<iostream> using namespace std; const int need=(1e6)+5; typedef int deq[need]; deq dqmax,dqmin; int topmax,backmax=1,topmin,backmin=1; int a[need],ansmax[need]={-1e9},ansmin[need]={1e9}; inline void in_(int &d) { bool mark=false;char t=getchar(); while(t<'0'||t>'9'){if(t=='-') mark=true;t=getchar();} for(d=0;t>='0'&&t<='9';t=getchar())d=(d<<3)+(d<<1)-'0'+t; if(mark) d=-d; } char o[100]; inline void out_(int x) { int l=1; if(x<0) x=-x,putchar('-'); if(!x) putchar('0'); for(;x;x/=10) o[l++]=x%10+'0'; for(l--;l;l--)putchar(o[l]); putchar(' '); } int main() { //freopen("a.txt","r",stdin); //freopen("b.txt","w",stdout); int n,k;scanf("%d%d",&n,&k); for(int i=1;i<=k;i++) { in_(a[i]);//scanf("%d",&a[i]); while(topmax!=backmax-1&&a[dqmax[topmax]]<a[i]) topmax--; while(topmin!=backmin-1&&a[dqmin[topmin]]>a[i]) topmin--; dqmax[++topmax]=i; dqmin[++topmin]=i; ansmax[i]=max(a[i],ansmax[i-1]); ansmin[i]=min(a[i],ansmin[i-1]); } for(int i=k+1;i<=n;i++) { in_(a[i]);//scanf("%d",&a[i]); while(topmax!=backmax-1&&a[dqmax[topmax]]<a[i]) topmax--; while(topmin!=backmin-1&&a[dqmin[topmin]]>a[i]) topmin--; dqmax[++topmax]=i; dqmin[++topmin]=i; if(topmax!=backmax-1&&dqmax[backmax]<i-k+1) backmax++; if(topmin!=backmin-1&&dqmin[backmin]<i-k+1) backmin++; ansmax[i]=a[dqmax[backmax]]; ansmin[i]=a[dqmin[backmin]]; } for(int i=k;i<=n;i++) out_(ansmin[i]);//printf("%d ",ansmin[i]); putchar(10); for(int i=k;i<=n;i++) out_(ansmax[i]);//printf("%d ",ansmax[i]); }