首页 > 代码库 > 洛谷P1886 滑动窗口（POJ.2823 Sliding Window）（区间最值）
洛谷P1886 滑动窗口（POJ.2823 Sliding Window）（区间最值）
To 洛谷.1886 滑动窗口 To POJ.2823 Sliding Window
题目描述
现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
输入输出格式
输入格式：
输入一共有两行，第一行为n,k。
第二行为n个数(<INT_MAX).
输出格式：
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
输入样例#1：
8 31 3 -1 -3 5 3 6 7
输出样例#1：
-1 -3 -3 -3 3 33 3 5 5 6 7
说明
50%的数据，n<=10^5
100%的数据，n<=10^6
代码：
洛谷70分TLE的线段树
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=1000005; 5 6 int n,k,From,To,Min[N<<2],Max[N<<2]; 7 8 void read(int &now) 9 {10 now=0;int f=1;char c=getchar();11 while(c<‘0‘||c>‘9‘)12 {13 if(c==‘-‘)f=-1;14 c=getchar();15 }16 while(c>=‘0‘&&c<=‘9‘)now=now*10+c-‘0‘,c=getchar();17 now*=f;18 }19 20 inline void PushUp(int rt)21 {22 Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);23 Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);24 }25 26 void Build(int l,int r,int rt)27 {28 if(l==r)29 {30 int t;31 read(t);32 Min[rt]=Max[rt]=t;33 return;34 }35 int m=(l+r)>>1;36 Build(l,m,rt<<1);37 Build(m+1,r,rt<<1|1);38 PushUp(rt);39 }40 41 int QueryMax(int l,int r,int rt,int L,int R)42 {43 if(L<=l && r<=R) return Max[rt];44 int m=(l+r)>>1,res=(1<<31);45 if(L<=m) res=max(res,QueryMax(l,m,rt<<1,L,R));46 if(m<R) res=max(res,QueryMax(m+1,r,rt<<1|1,L,R));47 return res;48 }49 50 int QueryMin(int l,int r,int rt,int L,int R)51 {52 if(L<=l && r<=R) return Min[rt];53 int m=(l+r)>>1,res=(1<<30);54 if(L<=m) res=min(res,QueryMin(l,m,rt<<1,L,R));55 if(m<R) res=min(res,QueryMin(m+1,r,rt<<1|1,L,R));56 return res;57 }58 59 int main()60 {61 read(n);read(k);62 Build(1,n,1);63 //From=1;To=k;64 for(register int i=1;i<=n-k+1;i++)//,From++,To++65 printf("%d ",QueryMin(1,n,1,i,i+k-1));66 printf("\n");67 //From=1;To=k;68 for(register int i=1;i<=n-k+1;i++)//,From++,To++69 printf("%d ",QueryMax(1,n,1,i,i+k-1));70 return 0;71 }
常数优化十分可观的zkw线段树（然而我不会用）
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=1000005; 5 6 int n,k,M,Tree[N<<2]; 7 8 void read(int &now) 9 {10 now=0;int f=1;char c=getchar();11 while(c>‘9‘||c<‘0‘)12 {13 if(c==‘-‘)f=-1;14 c=getchar();15 }16 while(c>=‘0‘&&c<=‘9‘)now=(now<<3)+(now<<1)+c-‘0‘,c=getchar();17 now*=f;18 }19 20 void BuildMin(int n)21 {22 for(int i=M-1;i;--i)23 Tree[i]=min(Tree[i<<1],Tree[i<<1|1]);24 }25 26 void BuildMax(int n)27 {28 for(int i=M-1;i;--i)29 Tree[i]=max(Tree[i<<1],Tree[i<<1|1]);30 }31 32 int QueryMin(int s,int t,int res)33 {34 for(s+=M,t+=M;s^t^1;s>>=1,t>>=1)35 {36 if(~s&1) res=min(res,Tree[s^1]);37 if(t&1) res=min(res,Tree[t^1]);38 }39 return res;40 }41 42 int QueryMax(int s,int t,int res)43 {44 for(s+=M,t+=M;s^t^1;s>>=1,t>>=1)45 {46 if(~s&1) res=max(res,Tree[s^1]);47 if(t&1) res=max(res,Tree[t^1]);48 }49 return res;50 }51 52 int main()53 {54 read(n);read(k);55 for(M=1;M<=n+1;M<<=1);56 for(int i=M+1;i<=M+n;i++)57 read(Tree[i]);58 BuildMin(n);59 for(int i=0;i<=n-k;++i)60 printf("%d ",QueryMin(i,i+k+1,1e9));61 printf("\n");62 BuildMax(n);63 for(int i=0;i<=n-k;++i)64 printf("%d ",QueryMax(i,i+k+1,-1e9));65 return 0;66 }
洛谷P1886 滑动窗口（POJ.2823 Sliding Window）（区间最值）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。