Sliding Window
Time Limit: 12000MS | Memory Limit: 65536K | |
Total Submissions: 32563 | Accepted: 9681 | |
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.
The array is [1 3 -1 -3 5 3 6 7], and k is 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 |
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
题意:
有N(1到10^6)个数,每K(1到N)个数一组。求出每组的最小值和最大值,最小值和最大值分别一行输出。
思路:
线段树基础题。线段树维护最大值最小值。
AC:
#include<stdio.h> #define MAX 1000005 typedef struct { int l; int r; int min; int max; }node; node no[MAX*5]; int num[MAX]; int fma,fmi; void build(int from,int to,int i) { int mid=(from+to)/2; no[i].l=from; no[i].r=to; if(from==to) { no[i].max=num[from]; no[i].min=num[from]; return; } build(from,mid,2*i); build(mid+1,to,2*i+1); no[i].max=(no[2*i].max>no[2*i+1].max?no[2*i].max:no[2*i+1].max); no[i].min=(no[2*i].min<no[2*i+1].min?no[2*i].min:no[i*2+1].min); } void findmax(int from,int to,int i) { int mid=(no[i].l+no[i].r)/2; if(from==no[i].l&&to==no[i].r) { fma=(fma>no[i].max?fma:no[i].max); return; } if(from>=mid+1) findmax(from,to,2*i+1); if(to<=mid) findmax(from,to,2*i); if(from<=mid&&to>=mid+1) { findmax(from,mid,2*i); findmax(mid+1,to,2*i+1); } } void findmin(int from,int to,int i) { int mid=(no[i].l+no[i].r)/2; if(from==no[i].l&&to==no[i].r) { fmi=(fmi>no[i].min?no[i].min:fmi); return; } if(from>=mid+1) findmin(from,to,2*i+1); if(to<=mid) findmin(from,to,2*i); if(from<=mid&&to>=mid+1) { findmin(from,mid,2*i); findmin(mid+1,to,2*i+1); } } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&num[i]); build(1,n,1); for(int i=1;i<=n-m+1;i++) { fmi=num[i]; //WA了N遍,就是因为赋值这里 //一开始赋值fmi=MAX; //因为fmin是int型的,存MAX不够存 findmin(i,i+m-1,1); printf("%d",fmi); i==n-m+1?printf("\n"):printf(" "); } for(int i=1;i<=n-m+1;i++) { fma=num[i]; //同理,这里也不可以赋值为fma=-MAX findmax(i,i+m-1,1); printf("%d",fma); i==n-m+1?printf("\n"):printf(" "); } return 0; }
总结:
1.细节的错误现在遇到得比较多,都是不容易发现的错误;
2.不是多输入和输出格式的错误,赋值的时候要注意要在数据范围内赋值。
相关推荐
滑动窗口软件代码,UDP Sliding Window Protocol
Sliding Window_(System Approach 4ed)
Sliding window ,滑窗协议 ,实验报告,代码,实验截图等,仅供参考学习
Qt5.5.1+msvc2013使用QSplitter控件实现滑动窗口,根据程序需求可设置为固定和可移动
这是来自poj的一道关于单调队列的题目。分为max_qu和min_qu两部分来做。
sliding_window算法的python版本,分享给有需要的人
基于滑动窗口的三维手指检测和跟踪算法,吴俊,乔文静,本文提出了一种面向RGB-D深度图像序列的基于滑动窗口的三维手指检测跟踪算法 (3dFDT) 。微软的Kinect被作为获取三维深度图像序列的摄像�
Sliding Window Protocol Implementatoin
TCP Sliding Window滑动窗口协议演示动画,Flash播放,可以调整参数
2. Pattern Sliding Window.zip
一篇流数据分析方面的经典SCI论文,2013年发表的
滑动窗口协议解析
var slidingWindow = SlidingWindow ( alloc , free , options ) ; alloc是一个分配东西的函数。 它接收两个参数:第一个参数是要分配的块的index 。 第二个参数是一个可选参数,可以在move()第二个参数处传输。 ...
本文详细分析了基于滑动窗口的视觉slam或者视觉里程计方案的一致性问题
Sliding-window-topk.ppt
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
Sliding Window:实现使用GBN协议和UDP进行通信的发送方和接收方 一点警告:这里发生了很多内存泄漏,因此克隆它修复并从中获得乐趣。 我有点想念的另一件事是解释滑动部分,它确实是分块完成的。
sliding window and active constellation extension for fbmc oqam signal
MATLAB典型代码 (示例面部检测结果来自anXDdd。) 项目4:带有滑动窗口的人脸检测 简短的 截止时间: 1月1日,晚上11:59。 所需文件:results / index.md和代码/ ...滑动窗口模型在概念上很简单:将所有图像块独立地...
QSplitter实现伸缩滑动窗口,完整的代码,在centos6.6上测试运行过。