P1886 滑动窗口

admin

https://www.luogu.org/problemnew/show/P1886

题目描述
现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：
The array is [1 3 -1 -3 5 3 6 7], and k = 3.

位置	最大值
[1  3  -1] -3  5  3  6  7	3
1 [3  -1  -3] 5  3  6  7	3
1  3 [-1  -3  5] 3  6  7	5
1  3  -1 [-3  5  3] 6  7	5
1  3  -1  -3 [5  3  6] 7	6
1  3  -1  -3  5 [3  6  7]	7

输入输出格式
输入格式：
输入一共有两行，第一行为n,k。

第二行为n个数(<INT_MAX).

输出格式：
输出共两行，第一行为每次窗口滑动的最小值

第二行为每次窗口滑动的最大值

输入输出样例
输入样例#1：
8 3
1 3 -1 -3 5 3 6 7
输出样例#1：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
说明
50%的数据，n<=10^5

100%的数据，n<=10^6

admin

这是一个很好的简单的高级数据结构的训练题，可以用很多种方法很做，
1、典型的单调队列题，用一个队列维护，新加入的数字前，先删掉比他大的元素，要是队列的长度大于k，则队头元素删掉。这样队列里面的就是最大值。
2、ST表求最大值最小值显然是可行的，每次挪动了一个，还可以继承前面计算下来的f(i,j)
3、线段树来做此题有点大材小用，但是训练下代码能力也是不错的。4、大根堆：扫描的时候，新元素加入堆，如果发现堆顶元素不在当前的扫描区间内就pop堆顶元素，知道堆顶元素在扫描区间内，输出答案。

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. const int M=1000010;
   
4. int n,k,b,j=1;
   
5. int mina[M],maxa[M];
   
6. struct sque
   
7. {
   
8.     int a[M],head,tail;
   
9.     int q[M],p[M];
   
10.     void read()
    
11.     {
    
12.         cin>>n>>k;
    
13.         for(int i=1;i<=n;i++)
    
14.             cin>>a[i];
    
15.     }
    
16.     void findmax()
    
17.     {
    
18.         head=1;
    
19.         tail=0;
    
20.         for(int i=1;i<=n;i++)
    
21.         {
    
22.             while(q[tail]<=a[i] && head<=tail)tail--;
    
23.             q[++tail]=a[i];
    
24.             p[tail]=i;
    
25.             while(p[head]<=i-k)
    
26.                 head++;
    
27.             if(i>=k)cout<<q[head]<<" ";
    
28.         }
    
29.         cout<<endl;
    
30.     }
    
31.     void findmin()
    
32.     {
    
33.         head=1;
    
34.         tail=0;
    
35.         for(int i=1;i<=n;i++)
    
36.         {
    
37.             while(q[tail]>=a[i] && head<=tail)tail--;
    
38.             q[++tail]=a[i];
    
39.             p[tail]=i;
    
40.             while(p[head]<=i-k)
    
41.                 head++;
    
42.             if(i>=k)cout<<q[head]<<" ";
    
43.         }
    
44.         cout<<endl;
    
45.     }
    
46. }q;
    
47. int main()
    
48. {
    
49.     q.read();
    
50.     q.findmin();
    
51.     q.findmax();
    
52. }
    

复制代码

admin

单调队列经典题