求m区间的最小值

题目描述

一个含有n项的数列(n<=2000000),求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始,若前面没有数则输出0。

输入格式

第一行两个数n,m。

第二行,n个正整数,为所给定的数列。

输出格式

n行,第i行的一个数ai,为所求序列中第i个数前m个数的最小值。

输入输出样例

输入

6 2
7 8 1 4 3 2

输出

0
7
7
1
1
3

说明/提示

m ≤ n ≤ 2000000 m≤n≤2000000 mn2000000
a i ≤ 3 × 1 0 7 a_i\leq 3\times 10^7 ai3×107

单调队列过一遍就出来了,
开一个双端队列
对于每一个数存下其下表,从1开始扫,
每次把数放到队尾,同时如果队尾比当前值大就让队尾出队,直到小于等于当前数,
这样从队头开始扫的时候数字下标和数值都是是递增的。
然后我们对于下标大于i-m+1令其出队
最后的队头就是当前下标时的答案

#include<bits/stdc++.h>

#define ll long long
#define MAXN 5000100
#define N 1001
#define INF 0x3f3f3f3f
#define gtc() getchar()

using namespace std;

template <class T>
inline void read(T &s){ 
	s = 0; T w = 1, ch = gtc();
	while(!isdigit(ch)){ if(ch == '-') w = -1; ch = gtc();}
	while(isdigit(ch)){ s = s * 10 + ch - '0'; ch = gtc();}
	s *= w;
}

template <class T>
inline void write(T x){ 
    if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x/10);
    putchar(x % 10 + '0');
}

int n, m;
struct node{ 
	int w, id;
}a[MAXN];

deque<node> q;
int qu[MAXN];

int main()
{ 
	read(n), read(m);
	for(int i = 1; i <= n; ++i){ 
		read(a[i].w), a[i].id = i;
	}
	qu[1] = 0;
	for(int i = 1; i < n; ++i){ 
		while(!q.empty() && q.back().w >= a[i].w) q.pop_back();
		q.push_back(a[i]);
		while(!q.empty() && q.front().id < i-m+1) q.pop_front();
		qu[i] = q.front().w;
	}
	for(int i = 0; i < n; ++i){ 
		write(qu[i]); puts("");
	}
	return 0;
}
    原文作者:BIGBIGPPT
    原文地址: https://blog.csdn.net/BIGBIGPPT/article/details/102966221
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞