注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

Sliding Window  

2012-07-12 22:46:59|  分类: 线段树 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description

An array of size n ≤ 10^6 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 positionMinimum valueMaximum value
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

Your task is to determine the maximum and minimum values in the sliding window at each position.


Input

There are N cases(1 <= N < 10).
For each case, it 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. 
Input until EOF.

Output

There are two lines in the output for each case. 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.

Be careful that in the end of each line, there's no space " ".

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


开始研究线段树。这题当然可以不用线段树做。
一开始一直WA,发现是边界的问题搞错了。= =又是这样,关于边界的处理总会卡这么一下子。。
下面是我的代码:


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define MAXN 1000001
#define LC(a) ((a << 1) + 1) ///< 左儿子下标
#define RC(a) ((a << 1) + 2) ///< 右儿子下标
#define MID(a, b) ((a + b) >> 1) ///< 求中点
struct node
{
int l,r;
int mid;
int _max;
int _min;

}T[MAXN * 4];

int num[MAXN];

void create(int p, int l, int r)
{
T[p].l = l, T[p].r = r, T[p].mid = MID(l, r);
if(l == r)
{
T[p]._max = num[l - 1];
T[p]._min = num[l - 1];
return;
}
create(LC(p), l, T[p].mid);
create(RC(p), T[p].mid + 1, r);
T[p]._max = max(T[LC(p)]._max , T[RC(p)]._max);
T[p]._min = min(T[LC(p)]._min, T[RC(p)]._min);
}
//这里的功能是更新一段的和.
void update(int p, int i, int num) ///< num有正负
{
if(T[p].l == T[p].r)
{
T[p]._min = num;
T[p]._max = num;
//break;
return ;
}
if(i <= T[p].mid) update(LC(p), i, num);
else update(RC(p), i, num);

/** 更新该节点的sum */
T[p]._max= max(T[LC(p)]._max , T[RC(p)]._max);
T[p]._min= min(T[LC(p)]._min , T[RC(p)]._min);
}

int query_max(int p, int l, int r)
{
if(T[p].l == l && T[p].r == r) return T[p]._max;

if(r <= T[p].mid) return query_max(LC(p), l, r);
else
if(l > T[p].mid) return query_max(RC(p), l, r);
else return max(query_max(LC(p), l, T[p].mid) , query_max(RC(p), T[p].mid + 1, r));
}



int query_min(int p, int l, int r)
{
if(T[p].l == l && T[p].r == r) return T[p]._min;

if(r <= T[p].mid) return query_min(LC(p), l, r);
else
if(l > T[p].mid) return query_min(RC(p), l, r);
else return min(query_min(LC(p), l, T[p].mid) , query_min(RC(p), T[p].mid + 1, r));
}


int main()
{
int n,k;
while(cin>>n>>k)
{
for(int i = 0 ;i < n;i ++) scanf("%d",&num[i]);
create(0,1,n);

for(int i = 1;i <= n - k;i ++)
{

printf("%d ",query_min(0,i,i + k - 1));
}

printf("%d\n",query_min(0,n - k + 1,n));

for(int i = 1;i <= n - k ;i ++)
{
printf("%d ",query_max(0,i,i + k - 1));

}

printf("%d\n",query_max(0,n - k + 1,n));
}
return 0;
}

/*
n,k
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
*/



  评论这张
 
阅读(128)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018