[洛谷P1440]求m区间内的最小值

题目大意：给你n个数，求出每个数前m位的最小值

题解：单调队列，用一个可以双向弹出的队列来存一串数，满足里面的数具有单调性，我们可以假设它是单调递增的，即求最小的数。那么可以把要插入的这个数与队尾元素比较，如果队尾的数大，那么插入它就不满足单调性了，那么我们就从队尾删除元素，直到比队尾元素大。这样就可以满足要求。如果队首元素已经超出了m的范围，就从队首删除元素，队首的元素就一直是答案。

#include<cstdio>

using namespace std;

int n,m;

int q[2001000],h,t;

int s[2001000];

int main(){

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++)scanf("%d",&s[i]);

	puts("0");

	q[h=t=1]=1;

	for (int i=2;i<=n;i++){

		if (i-q[h]>m)h++;

		printf("%d\n",s[q[h]]);

		while (h<=t&&s[i]<s[q[t]])t--;

		q[++t]=i;

	}

	return 0;

}

巴特西

[洛谷P1440]求m区间内的最小值

最新文章

热门文章