poj--2823 Sliding Window（优先队列 |

poj--2823 Sliding Window（优先队列 | | 线段树）

Description

An array of size n ≤ 10 ⁶ 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
题意：给一个数列分别从（1-->n-k）开始求之后的k项的最大值和最小值，然后打印出来
思路1：用优先队列对进入队列的一系列的数进行排序，然后取出队首元素。有关优先队列的讲解博客http://www.cnblogs.com/summerRQ/articles/2470130.html
AC代码：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 const int maxn=1000000+5;
 8 int l[maxn],r[maxn],s[maxn];
 9 struct cmp1
10 {
11     bool operator() (const int a1,const int a2)
12     {
13         return s[a1]>s[a2];
14     }
15 };
16 struct cmp2
17 {
18     bool operator()(const int a1,const int a2)
19     {
20         return s[a1]<s[a2];
21     }
22 };
23 int main()
24 {
25     int n,k;
26     while(~scanf("%d%d",&n,&k))
27     {
28         priority_queue<int ,vector<int>,cmp1>Q1;//定义优先队列
29         priority_queue<int ,vector<int>,cmp2>Q2;
30         for(int i=1; i<=n; i++)
31             scanf("%d",&s[i]);
32             if(n<k)
33                 k=n;
34         for(int i=1; i<k; i++)
35         {
36             Q1.push(i);
37             Q2.push(i);
38         }
39         for(int i=k; i<=n; i++)
40         {
41             Q1.push(i);
42             Q2.push(i);
43             while(i-Q1.top()>=k)//当队首在[i-k+1,k]之外时就把队首出队
44             Q1.pop();
45             while(i-Q2.top()>=k)
46             Q2.pop();
47             l[i-k]=s[Q1.top()];
48             r[i-k]=s[Q2.top()];
49         }
50         for(int i=k; i<n; i++)
51             printf("%d ",l[i-k]);
52         printf("%d
",l[n-k]);
53         for(int i=k; i<n; i++)
54             printf("%d ",r[i-k]);
55         printf("%d
",r[n-k]);
56     }
57     return 0;
58 }

View Code

思路2：用线段树将其数值存入线段树中，分别用maxn和minn分别更新节点的最大值和最小值，最后对【i，i+k-1】进行搜索不断地更新最大值和最小值用数组存一下。最后注意这个题在poj上用线段树写要用c++编译器交，用G++交是超时的。

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int a[1100005],ansmax,ansmin;
 5 struct note
 6 {
 7     int l,r,pmax,pmin;
 8 } note[2200010];
 9 int build(int l,int r,int k)
10 {
11     if(l==r)
12     {
13         note[k].l=l;
14         note[k].r=r;
15         note[k].pmax=-1000000;
16         note[k].pmin=10000000;
17         return 0;
18     }
19     note[k].l=l;
20     note[k].r=r;
21     note[k].pmax=-1000000;
22     note[k].pmin=10000000;
23     int mid=(l+r)/2;
24     build(l,mid,k*2);
25     build(mid+1,r,k*2+1);
26     return 0;
27 }
28 int ins(int n,int d,int k)
29 {
30     if(note[k].l==note[k].r&&note[k].l==d)
31     {
32         note[k].pmax=n;
33         note[k].pmin=n;
34         return 0;
35     }
36     int mid=(note[k].l+note[k].r)/2;
37     if(d<=mid) ins(n,d,k*2);
38     else ins(n,d,2*k+1);
39     note[k].pmax=max(note[2*k].pmax,note[2*k+1].pmax);
40     note[k].pmin=min(note[2*k].pmin,note[2*k+1].pmin);
41     return 0;
42 }
43 int sea(int l,int r,int k)
44 {
45     if(note[k].l==l&&note[k].r==r)
46     {
47         ansmax=max(ansmax,note[k].pmax);
48         ansmin=min(ansmin,note[k].pmin);
49         return 0;
50     }
51     int mid=(note[k].l+note[k].r)/2;
52     if(mid>=r) sea(l,r,2*k);
53     else if(mid<l) sea(l,r,2*k+1);
54     else
55     {
56         sea(l,mid,2*k);
57         sea(mid+1,r,2*k+1);
58     }
59     return 0;
60 }
61 int main()
62 {
63     int n,k,x;
64     while(~scanf("%d%d",&n,&k))
65     {
66         build(1,n,1);
67         for(int i=1; i<=n; i++)
68         {
69             scanf("%d",&x);
70             ins(x,i,1);
71         }
72         for(int i=1; i<=n-k+1; i++)
73         {
74             ansmax=-10000000;//在主函数里面进行定义
75             ansmin=100000000;
76             sea(i,i+k-1,1);
77             a[i]=ansmax;
78             printf("%d%c",ansmin,i==(n-k+1)?'
':' ');
79         }
80         for(int i=1;i<=n-k+1;i++)
81             printf("%d%c",a[i],i==(n-k+1)?'
':' ');
82     }
83     return 0;
84 }

View Code