Posted on 2008-03-28 10:28
王大头 阅读(527)
评论(1) 编辑 收藏 引用
Time Limit: 12000MS Memory Limit: 65536K
Total Submissions: 4531 Accepted: 983
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
|
| 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
解题思路：
滚动数组＋堆排序
如下面的smax数组，整个是一个排序堆，前半段是
排序用的附加数据，后面半段是一个滚动数组，就
是滑动窗口的所有数据。效率一般，应该还有优化
的余地，主要是把计算smin和smax的过程分开，
对于对上层堆没有影响的数据，可以直接退出循环
#include <stdio.h>
#include <stdlib.h>
#define MIN(x, y) ((x) < (y)) ? (x) : (y)
#define MAX(x, y) ((x) > (y)) ? (x) : (y)
int main()
{
int i, j, k, m, n, off, *smax, *smin, *sflag, *maxout, *minout;
int t;
scanf("%d %d", &n, &k);
off = k, i = 1;
while(off /= 2) i++;
off = 1;
while(i--) off *= 2;
smax = (int *)malloc(sizeof(int) * (off * 2 - 1));
smin = (int *)malloc(sizeof(int) * (off * 2 - 1));
sflag = (int *)calloc(off * 2 - 1, sizeof(int));
maxout = (int *)malloc(sizeof(int) * (n - k + 1));
minout = (int *)malloc(sizeof(int) * (n - k + 1));
for(i = 0; i < n; i++) {
j = off - 1 + (i % k);
scanf("%d", &smax[j]);
smin[j] = smax[j];
sflag[j] = 1;
while(j > 0) {
if(j % 2) {
if(sflag[j + 1]) {
sflag[j / 2] = 1;
m = MAX(smax[j], smax[j + 1]);
smax[j / 2] = m;
m = MIN(smin[j], smin[j + 1]);
smin[j / 2] = m;
}
else {
sflag[j / 2] = 1;
smax[j / 2] = smax[j];
smin[j / 2] = smin[j];
}
j /= 2;
}
else {
sflag[(j - 1) / 2] = 1;
m = MAX(smax[j - 1], smax[j]);
smax[(j - 1) / 2] = m;
m = MIN(smin[j - 1], smin[j]);
smin[(j - 1) / 2] = m;
j = (j - 1) / 2;
}
}
if(i < k - 1)
continue;
maxout[i - k + 1] = smax[0];
minout[i - k + 1] = smin[0];
}
for(i = 0; i <= n - k; i++)
printf("%d%c", minout[i], (i < n - k) ? ' ' : '\n');
for(i = 0; i <= n - k; i++)
printf("%d%c", maxout[i], (i < n - k) ? ' ' : '\n');
free(smax);
free(smin);
free(sflag);
free(maxout);
free(minout);
}