一个含有n项的数列(n<=2000000),求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始,若前面没有数则输出0。
输入格式:
第一行两个数n,m。
第二行,n个正整数,为所给定的数列。
输出格式:
n行,第i行的一个数ai,为所求序列中第i个数前m个数的最小值。
输入样例#1:
6 2
7 8 1 4 3 2
输出样例#1:
0
7
7
1
1
3
【数据规模】
m≤n≤2000000
单调队列的裸题。
注意判断好队列里面元素的数量
维护递增序列
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<map>
6 using namespace std;
7 int h=1,t=1;
8 int a[2000001];
9 struct node
10 {
11 int q[3000001];
12 int size()
13 {
14 return t-h;
15 }
16 void popt()
17 {
18 q[t]=0;
19 t--;
20 }
21 void poph()
22 {
23 h++;
24 }
25 int front()
26 {
27 return q[h];
28 }
29
30 void push(int x)
31 {
32 if(a[x]>=a[q[t]])
33 {
34 t++;
35 q[t]=x;
36 }
37 else
38 {
39 while(a[x]<a[q[t]]&&t>=h)
40 {
41 q[t]=0;
42 t--;
43 }
44 t++;
45 q[t]=x;
46 }
47
48 }
49 }que;
50 int main()
51 {
52 int n,m,x;
53 scanf("%d%d",&n,&m);
54 que.q[1]=1;
55 for(int i=1;i<=n;i++)
56 {
57
58 scanf("%d",&x);
59 a[i]=x;
60
61 if(i==1)
62 {printf("0\n");
63 continue;}
64
65 printf("%d\n",a[que.front()]);
66
67 if(que.front()<=i-m)
68 que.poph();
69
70
71
72 que.push(i);
73 }
74 return 0;
75 }