P1440 求m区间内的最小值
题目描述
一个含有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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-05-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录