| Time Limit: 12000MS | Memory Limit: 65536K | |
| Total Submissions: 35408 | Accepted: 10476 | |
| Case Time Limit: 5000MS | ||
Description
| 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
Output
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
思路：据说是单调队列，我用线段树过的。。。
1 #include<iostream> 2 #include<cstdio> 3 #define MAX 1000005 4 using namespace std; 5 typedef struct 6 { 7 int left, right, mid, min, max; 8 }NodeTree; 9 NodeTree node[4*MAX]; 10 int maxn, minn, min_num[MAX],max_num[MAX]; 11 void BuildTree(int k, int l, int r) 12 { 13 node[k].left = l; 14 node[k].right = r; 15 node[k].mid = (l + r) >> 1; 16 node[k].max = -10000000; 17 node[k].min = 10000000; 18 if(l == r) 19 return; 20 int mid = (l + r) >> 1; 21 BuildTree(k << 1, l, mid); 22 BuildTree(k << 1|1, mid+1, r); 23 } 24 25 void UpdateTree(int k, int l, int r, int num) 26 { 27 if(node[k].max < num) 28 node[k].max = num; 29 if(node[k].min > num) 30 node[k].min = num; 31 if(node[k].left == node[k].right) 32 return; 33 if(node[k].mid < l) 34 UpdateTree(k << 1|1, l, r, num); 35 else if(node[k].mid >= r) 36 UpdateTree(k << 1, l, r, num); 37 else 38 { 39 UpdateTree(k << 1, l, node[k].mid, num); 40 UpdateTree(k << 1|1, node[k].mid + 1, r, num); 41 } 42 } 43 44 void GetResult(int k, int l, int r) 45 { 46 if(node[k].left ==l && node[k].right==r) 47 { 48 minn = min(minn, node[k].min); 49 maxn = max(maxn, node[k].max); 50 return; 51 } 52 if(node[k].mid < l) 53 GetResult(k << 1|1, l, r); 54 else if(node[k].mid >= r) 55 GetResult(k << 1, l, r); 56 else 57 { 58 GetResult(k << 1, l, node[k].mid); 59 GetResult(k << 1|1, node[k].mid + 1, r); 60 } 61 } 62 63 int main(int argc, char const *argv[]) 64 { 65 int n, k, i, temp; 66 freopen("in.c", "r", stdin); 67 while(~scanf("%d%d", &n, &k)) 68 { 69 BuildTree(1, 1, n); 70 for(i = 1;i <= n;i ++) 71 { 72 scanf("%d", &temp); 73 UpdateTree(1, i, i, temp); 74 } 75 int j = 0; 76 for(i = 1;i < n - k + 2;i ++) 77 { 78 minn = 10000000; 79 maxn = -10000000; 80 GetResult(1, i, i+k-1); 81 min_num[j] = minn; 82 max_num[j ++] = maxn; 83 } 84 for(i = 0;i < n - k;i ++) 85 printf("%d ", min_num[i]); 86 printf("%d\n", min_num[i]); 87 for(i = 0;i < n - k;i ++) 88 printf("%d ", max_num[i]); 89 printf("%d\n", max_num[i]); 90 } 91 return 0; 92 }
原文：http://www.cnblogs.com/anhuizhiye/p/3597320.html