POJ2823_Slidingwindow_solution

发布时间:2016-12-8 14:04:32 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ2823_Slidingwindow_solution",主要涉及到POJ2823_Slidingwindow_solution方面的内容,对于POJ2823_Slidingwindow_solution感兴趣的同学可以参考一下。

题目链接http://poj.org/problem?id=2823Description An array of size n ≤ 106 is given to you. There is a sliding window of sizek which is moving from the very left of the array to the very right. You can only see thek numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and k is 3. Window position Minimum value Maximum value [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 Your task is to determine the maximum and minimum values in the sliding window at each position. Input The input consists of two lines. The first line contains two integersn andk which are the lengths of the array and the sliding window. There aren integers in the second line. Output There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values. Sample Input 8 3 1 3 -1 -3 5 3 6 7 Sample Output -1 -3 -3 -3 3 3 3 3 5 5 6 7 Source POJ Monthly--2006.04.28, Ikki   最近在HDU上练习写线段树,其中就有这个题目,虽然看到N有10^6之多,还是傻傻地写了个线段树。写完后上网搜了下其他人的解法,发现线段树的写法真心都差不多,无非是建树、更新、查询,三个函数一贴就完了,实在没有什么新意。后来才知道这个题目其实最好的解法是双端队列。接下来我把两个解法的源代码都贴一下: #include<stdio.h> #define MAXN 1000005 #define MAXINF 2147483647 //定义一个无穷大的整数 struct treeInfo//线段树的结构体,保存管理区间与最值 { int left,right; int max,min; }; treeInfo segTree[3*MAXN];//数组稍微开大点,要不老是RE int n,k,arr[MAXN],resultMax[MAXN],resultMin[MAXN];//arr是原数组,resultMax保存最大值,resultMin保存最小值 int getMax(int a,int b) { return a>b?a:b; } int getMin(int a,int b) { return a<b?a:b; } void buildTree(int pos,int l,int r)//建树,就这个套路,熟练了闭着眼也能敲出来 { segTree[pos].left=l; segTree[pos].right=r; if(l==r) { segTree[pos].max=arr[l]; segTree[pos].min=arr[l]; return; } int mid=(l+r)/2; buildTree(pos<<1,l,mid); buildTree(pos<<1|1,mid+1,r); segTree[pos].max=getMax(segTree[pos<<1].max,segTree[pos<<1|1].max); segTree[pos].min=getMin(segTree[pos<<1].min,segTree[pos<<1|1].min); } void query(int pos,int l,int r,int num)//没有什么新意,找到满足的区间,然后去更新最大最小值,num是当前要更新的位置 { if(segTree[pos].left==l&&segTree[pos].right==r) { resultMax[num]=getMax(resultMax[num],segTree[pos].max); resultMin[num]=getMin(resultMin[num],segTree[pos].min); return; } int mid=(segTree[pos].left+segTree[pos].right)/2; if(r<=mid) query(pos<<1,l,r,num); else if(l>=mid+1) query(pos<<1|1,l,r,num); else { query(pos<<1,l,mid,num); query(pos<<1|1,mid+1,r,num); } } int main() { int i; while(scanf("%d%d",&n,&k)!=EOF) { arr[0]=MAXINF; for(i=1;i<=n;i++) scanf("%d",&arr[i]); buildTree(1,1,n); if(n<=k)//窗口很大,完全覆盖了整个数组,直接取整个数组的最值就可以了 { resultMax[1]=-MAXINF; resultMin[1]=MAXINF; query(1,1,n,1); printf("%d\n",resultMin[1]); printf("%d\n",resultMax[1]); continue; } for(i=0;i<=n-k+1;i++)//初始化一下 { resultMax[i]=-MAXINF;//把最大值赋一个无穷小 resultMin[i]=MAXINF;//把最小值赋一个无穷大 } query(1,1,k,1);//先获得第一个区间的最大值 for(i=2;i<=n-k+1;i++) { //这一段if-else是剪枝,不要也可以过,但是效率差一点 if(resultMax[i-1]!=arr[i-1]&&resultMin[i-1]!=arr[i-1])//如果前面一个k区间[i-1至(i-1)+k-1]这个区间的最大值与arr[i-1]没有关系,只要比较新加入的arr[i+k-1]元素就可以了 { resultMax[i]=getMax(arr[i+k-1],resultMax[i-1]);//比较一下resultMax[i-1]与arr[i+k-1]就可以了 resultMin[i]=getMin(arr[i+k-1],resultMin[i-1]);//比较一下resultMin[i-1]与arr[i+k-1]就可以了 continue; /* 这里举个例子说明一下:1 3 -1 -3 假设k是3,开始窗口覆盖1 3 -1,最大值是3,最小值-1,与第一个元素1都没有关系,我们只要比较(3,-3)就可以获得最大值,比较(-1,-3)就是最小值 */ } else if(resultMax[i-1]<=arr[i+k-1]&&resultMin[i-1]!=arr[i-1])//前面获得的最大值没有将要加入的元素大,那最大值肯定就是新加入的元素 { //并且最小值与前面k区间的第一个元素没有关系,最小值不用更新 resultMax[i]=arr[i+k-1]; resultMin[i]=resultMin[i-1]; continue; /* 同样举个例子:3 -1 2 5 k是3,前面三个max=3,min=-1,因max<5,min=-1与第一个元素3没有关系,所以max=5,min=-1 */ } else if(resultMin[i-1]>=arr[i+k-1]&&resultMax[i-1]!=arr[i-1])//前面获得的最小值没有将要加入的元素小,那最小值就是新加入的元素 //并且最大值与前面的k区间没有关系,最大值不用更新 { resultMax[i]=resultMax[i]; resultMin[i]=arr[i+k-1]; continue; /* 看这个例子:-1 2 4 -4 k是3,前面三个max=4,min=-1,因min=-1>-4,并且max=4与第一个元素-1没有关系,所以min=-4,max=4 */ } query(1,i,i+k-1,i);//获得以第i个元素开始的k区间的最值 } //开始输出最小值 printf("%d",resultMin[1]); for(i=2;i<=n-k+1;i++) printf(" %d",resultMin[i]); printf("\n"); //开始输出最大值 printf("%d",resultMax[1]); for(i=2;i<=n-k+1;i++) printf(" %d",resultMax[i]); printf("\n"); } return 0; } /* 8 3 1 3 -1 -3 5 3 6 7 */ 接下来再贴一下双端队列的代码,代码尽量注释详细,这里也不用解释了。 #include<stdio.h> #define MAXN 1000005 int arr[MAXN],n,k; int max_que[MAXN],min_que[MAXN],ans_max[MAXN],ans_min[MAXN];//两个队列只保存元素的索引 int max_que_head,max_que_tail,min_que_head,min_que_tail; int main() { int i; while(scanf("%d%d",&n,&k)!=EOF) { max_que_head=max_que_tail=min_que_head=min_que_tail=1; max_que[1]=1;//假设初始状态最大、最小值都是arr[1] min_que[1]=1; for(i=1;i<=n;i++) { scanf("%d",&arr[i]); //先维护最大队列 while(arr[max_que[max_que_tail]]<=arr[i]&&max_que_head<=max_que_tail)//把队尾小于等于arr[i]的元素删除 max_que_tail--; max_que[++max_que_tail]=i;//把arr[i]放在队尾 if(max_que[max_que_head]<=i-k)//如果队首元素与当前元素相差k个位置以上,那么这个元素不在滑动窗口内,删除 max_que_head++; ans_max[i]=arr[max_que[max_que_head]];//队首元素是最大值 //接下来维护最小队列 while(arr[min_que[min_que_tail]]>=arr[i]&&min_que_head<=min_que_tail)//与最大队列维护操作一样,始终使队首是合法的最小值即可 min_que_tail--; min_que[++min_que_tail]=i; if(min_que[min_que_head]<=i-k) min_que_head++; ans_min[i]=arr[min_que[min_que_head]]; } //按格式输出最小值 printf("%d",ans_min[k]); for(i=k+1;i<=n;i++) printf(" %d",ans_min[i]); printf("\n"); //按格式输出最大值 printf("%d",ans_max[k]); for(i=k+1;i<=n;i++) printf(" %d",ans_max[i]); printf("\n"); } return 0; } 相比线段树,双端队列的代码更加简练,效率也更高,因为双端队列的复杂度是O(n),而线段树是nlog(n)。  

上一篇:JAVA第六弹(深入数组)
下一篇:sysobjects的相关内容

相关文章

相关评论