517pj训练-1

单调队列

poj 2823

思路,懒得打字,就复制了一段

1
但其实我们的移动也是有规律可循的,每次只向后移动一个数字,所以,我们在前一个区间内找到的最大值,首先判断一下是否还存在于当前区间,如果不存在那么就直接将该数字删除就好了,然后还有一个新的数字进入栈,看一下他是否是最大或最小。在找最小值的时候,我们每进入一个区间,首先要判断当前栈中的元素个数,首先保证要长度是k-1,因为后面还要插入一个新的数字,然后判断前面有没有比他大的,如果有的话,那么就把那个大的数字出栈,到最后让当前数字入栈,这样保证维护一个递增的栈,那么头上的数字永远是位于区间内的最小值,最大值的求解也是一样的道理。下面就是具体的代码实现了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int n,m,q[1000005],head,tail,a[1000005];
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return x*f;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
q[0]=1;
for(int i=1;i<=n;i++)
{
while(head<=tail&&a[i]<=a[q[tail]])tail--;
tail++;
q[tail]=i;
while(q[tail]-q[head]>=m)head++;
if(i>=m)cout<<a[q[head]]<<" ";
}
cout<<endl;
memset(q,0,sizeof(q));
head=tail=0;
q[0]=1;
for(int i=1;i<=n;i++)
{
while(head<=tail&&a[i]>=a[q[tail]])tail--;
tail++;
q[tail]=i;
while(q[tail]-q[head]>=m)head++;
if(i>=m)cout<<a[q[head]]<<" ";
}
}