求m区间内的最小值
题目描述:
一个含有n项的数列(n<=2000000),求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始,若前面没有数则输出0。
分析:
读题之后可以发现,这道题就是在求:
给出一个长度为n的序列a,求a中所有长度为m的连续子序列中的最小值
而针对这种问题,单调队列似乎是我们最好的选择。
单调队列,说是队列,却不符合队列“先进先出”的原则,它只是沿用了队列的思想,并具有一定的单调性,拥有一个队列头head和一个队列尾tail,用head和tail来控制队列的长度,筛选队列中的元素以及保持队列的单调性。
但怎样控制队列的长度,筛选队列中的元素以及保持队列的单调性呢?
这就是单调队列的实现了。
用样例来分析一下:
6 2 7 8 1 4 3 2
这样,我们就拥有了一个初始队列:7 8 1 4 3 2
拥有上帝视角的我们可以看出答案是:
0 7 7 1 1 3
这时候,我们发现,不论第一个元素是多少,它之前m个元素的最小值永远为0(因为它之前并没有元素),而最后一个元素是多少也没有关系(因为它之后并没有元素)。
所以我们只用找到第2个到第n个元素中每个前m个元素的最小值就可以了,那么单调队列的单调性也应该是递增的,我们就可以把队列里每个元素的序号放入单调队列操作,就可以得到答案了。
于是我们可以开始模拟了:
考虑第一个元素,i=1,head=1,tail=0,q[tail]=0,a[1]=7,a[1]>a[ q[tail] ],把a[1]放入不会破坏单调性,q[head]=0,这个元素距队首元素的距离为0,则队列为:1
考虑第二个元素,i=2,head=1,tail=1,q[tail]=1,a[2]=8,a[2]>a[ q[tail] ],把a[2]放入不会破坏单调性,q[head]=1,这个元素距队首元素的距离为1,则队列为:1 2
考虑第三个元素,i=3,head=1,tail=2,q[tail]=2,a[3]=1,但a[3]<a[ q[tail] ],把a[3]放入会破坏单调性,而a[3]<a[ q[tail] ],由于求最小值,所以只能将a[ q[tail=2] ]弹出队列来保证单调性了,而a[3]>a[ q[tail=1] ],这时再将a[3]放入就不会破坏单调性了,q[head]=1,这个元素距队首元素的距离为2,达到长度m=2了,这队列头head就向后移,则队列为:3。
以此类推,直到第n-1个,因为第n个后面没有元素,所以第n个不会进入队列,每次都输出队列头对应的元素值,就得到了答案。
代码实现:
#include <iostream> #include <cstdio> #include <cmath> #define maxn 2000005 using namespace std; int n,m; int a[maxn]; int q[maxn]; int head,tail; int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); head=1; tail=0; printf("0n");//第一个元素它之前并没有元素 for(int i=1;i<n;i++)//从1~n-1个,第n个不进队列 { while((head<=tail)&&((i-q[head])>=m)) head++;//控制队列的长度 while((head<=tail)&&(a[q[tail]]>=a[i])) tail--;//筛选队列中的元素 tail++; q[tail]=i;//保持队列的单调性 printf("%dn",a[q[head]]);//输出答案 } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600608.html