单调队列（求区间最值）

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
这是一道单调队列的题，我们借代码来理清思路。
首先要用一个双端队列来维护单调队列，对于这个题而言，后插入而且比队首元素小的元素肯定更优，因为它更新更好，而后插入而且比队尾元素大的元素需要保留在队尾，这些操作的前提是元素的可行性，即是在当前元素之前的m个之内。这样，每一个回合结束时输出一次就可以了。
一般情况下我们用手打双端队列而不去用STL，但下面这个代码是STL版的。

#include
#include
#include
#include
using namespace std;
int a;
int n,m,i,j;
struct dta
{int v,num;
};
deque  q;
int r()
{int ans=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){ans*=10;ans+=ch-'0';ch=getchar();}return ans*f;
}int main()
{n=r(),m=r();printf("0\n");for(i=1;iwhile(!q.empty()&&i-q.front().num>=m)q.pop_front();while(!q.empty()&&aprintf("%d\n",q.front().v);}return 0;
} 
/*
10 3
6 4 10 10 8 6 4 2 12 14
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！