PKU 2823 解题报告

Sliding Window

Time Limit: 12000MS Memory Limit: 65536K
Case Time Limit: 5000MS

Description

An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k 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 integers n and k which are the lengths of the array and the sliding window. There are n 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

题意:题目的要求是说,给出n个整数,第一行输出i~(i+k-1)之间(0<=i<=(n+k-1))每个区间的最小值,第二行类似的输出最大值。 分析:由于数据量非常大(n<=10^6)所以直接使用暴力肯定TLE,其实RP如果不高一样会TLE的,这是后话,等会儿再说。 这道题的做法很多,看过底下的discuss,有的用单调队列,有的用STL"两个优先队列水过",而我因为RP值不够在Winner Tree(胜者树)上纠结了好几天。

胜者树:
在树形选择排序中,利用锦标赛思想建立的树称为胜者树。在胜者树中,每个非终端节点存储的是左右孩子节点中的优胜者。

对胜者树的主要操作有

  1. 建树( O(n) )
  2. 查询最值( O(logn) )
  3. 动态更新 ( O(logn) )

因为查询和更新都是基于二分的思想,所以胜者树在求最值以及区间求最值还是比较高效的。

对于这道题只需要进行前两步操作即可,并且因为求最小值和最大值分开两行求,所以最终可以先求最小胜者树,然后在同一个数组上再求最大胜者树。 胜者树是一种完全二叉树,所以我们采用一维数组来存储树结构,自底向上建树,有数组下标来关联其父,左儿子,右儿子,兄弟等节点的信息。

例如,对于节点i有:

  1. 仅当i=1时,节点i为根节点.
  2. 当i>1时,其父节点为floor(i/2) (对i/2向下取整).
  3. 节点i的左右儿子节点分别为2i,2i+1.
  4. 当i为奇数且不为1时其左兄弟节点为i-1.
  5. 当i为偶数,节点i的右兄弟节点为i+1.

在建树的时候有一个比较困扰我的问题,就是如何确定整棵树需要多少空间。后来想了一下真的有些多余。看看下面这张图就明白了。

无论n是奇数还是偶数,建一棵胜者树都只需要2n-1的空间就够了(节点0不使用,所以需要2n的空间)。

以最小胜者树为例,根据上面的性质,建树的代码如下(n个元素存储在D[n]~D[2*n-1]的空间中):

	t=n*2;
      for(i=t-2;i>0;i-=2){
	  j=i+1;x=i>>1;
	  D[x]=D[i]<d[j]?D[i]:D[j];
      }

查询部分,可以使用递归或者奇偶缩进的办法自底向上查询。

	i=l;j=r;x=i;
	  while(i<=j){
	      if(D[x]>D[i]) x=i;
	      if(D[x]>D[j]) x=j;
	      if(i%2==1) ++i;
	      if(j%2==0) --j;
	      i=i>>1;j=j>>1;
	  }//奇偶缩进的方法
int tMin(int l,int r)
{
  if(l==r) return D[l];
  if(r==(l+1)) return (D[l]<=D[r]?D[l]:D[r]);
  int t1=0;t2=0;ll=l;rr=r;
  if(ll%2==1){
      t1=ll;
      ++ll;
  }
 
  if(rr%2==0){
      t2=rr;
      --rr;
  }
  int ans=tMin(D,ll>>1,(rr-1)>>1);
  if(t1) ans=D[t1]<=ans?D[t1]:ans;
  if(t2) ans=D[t2]<=ans?D[t2]:ans;
  return ans;
}//递归方式查询

关于这道题,还有一个值得注意的地方,无论你是使用那种方式查询,都不要用g++提交,两种方法用g++都会TLE,用C++都可以AC.因为这个问题,这道题我写了17次。

CODE 1

#include<stdio.h>
int D[2000000];
 
int main()
{
  int i,j,k,t,n,x;
  while(scanf("%d%d",&n,&k)!=EOF){
      t=2*n;
      for(i=n;i<t;++i)
	scanf("%d",D+i);//获取元素
 
      for(i=t-2;i>0;i-=2){
	  j=i+1;
	  D[i/2]=D[i]<d[j]?D[i]:D[j];//建最小胜者树
      }
      int l=n,r=n+k-1;
      while(r<t){
	  i=l;j=r;x=i;
	  while(i<=j){
	      if(D[x]>D[i]) x=i;
	      if(D[x]>D[j]) x=j;
	      if(i%2==1) ++i;//奇偶缩进
	      if(j%2==0) --j;
	      i=i>>1;j=j>>1;//右移一位,相当于i=i/2
	  }
	  printf("%d ",D[x]);
	  ++l;++r;
      }
      putchar('n');
 
      for(i=t-2;i>0;i-=2){
	  j=i+1;
	  D[i/2]=D[i]>D[j]?D[i]:D[j];//建最大胜者树
      }
      l=n;r=n+k-1;
      while(r<t){
	  i=l;j=r;x=i;
	  while(i<=j){
	      if(D[x]<d[i]) x=i;
	      if(D[x]<d[j]) x=j;
	      if(i%2==1) ++i;
	      if(j%2==0) --j;//奇偶缩进
	      i=i>>1;j=j>>1;
	  }
	  printf("%d ",D[x]);
	  ++l;++r;
      }
      putchar('n');
  }
  return 0;
}

CODE 2(使用递归)

#include<stdio.h>
 
int D[2000010];
int tMin(int l,int r)
{
  if(l==r) return D[l];
  if(r==(l+1)) return (D[l]<=D[r]?D[l]:D[r]);
  int t1=0,t2=0,ll=l,rr=r;
  if(ll%2==1){
      t1=ll;
      ++ll;
  }
 
  if(rr%2==0){
      t2=rr;
      --rr;
  }
  int ans=tMin(ll>>1,(rr-1)>>1);
  if(t1) ans=D[t1]<=ans?D[t1]:ans;
  if(t2) ans=D[t2]<=ans?D[t2]:ans;
  return ans;
}
 
int tMax(int l,int r)
{
  if(l==r) return D[l];
  if(r==(l+1)) return (D[l]>=D[r]?D[l]:D[r]);
  int t1=0,t2=0,ll=l,rr=r;
  if(ll%2==1){
      t1=ll;
      ++ll;
  }
 
  if(rr%2==0){
      t2=rr;
      --rr;
  }
  int ans=tMax(ll>>1,(rr-1)>>1);
  if(t1) ans=D[t1]>=ans?D[t1]:ans;
  if(t2) ans=D[t2]>=ans?D[t2]:ans;
  return ans;
}
 
int main()
{
  int i,j,k,t,n,x;
  while(scanf("%d%d",&n,&k)!=EOF)
    {
      t=2*n;
      for(i=n;i<t;i++)
	scanf("%d",D+i);
 
      for(i=t-2;i>=2;i-=2){
	  j=i+1;x=i>>1;
	  D[x]=D[i]<=D[j]?D[i]:D[j];
      }
 
      int l=n,r=n+k-1;
      if(r<t) printf("%d",tMin(l,r));
      ++l;++r;
      while(r<t){
	  printf(" %d",tMin(l,r));
	  ++l;++r;
      }
      putchar('n');
 
      for(i=t-2;i>=2;i-=2){
	  j=i+1;x=i>>1;
	  D[x]=D[i]>=D[j]?D[i]:D[j];
      }
      l=n;r=n+k-1;
      if(r<t) printf("%d",tMax(l,r));
      ++l;++r;
      while(r<t){
	  printf(" %d",tMax(l,r));
	  ++l;++r;
      }
      putchar('n');
    }
  return 0;
}

其实还有一个使用迭代来代替递归的版本,用了很多goto所以就不好意思贴出来了。

» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>