【洛谷】【单调队列】P2032 扫描

【题目描述：】

有一个 1 ∗ n 的矩阵，有 n 个正整数。

现在给你一个可以盖住连续的 k 的数的木板。

一开始木板盖住了矩阵的第 1 ∼ k 个数，每次将木板向右移动一个单位，直到右端与第 n 个数重合。

每次移动前输出被覆盖住的最大的数是多少。

【输入格式：】

第一行两个数，n，k，表示共有 n 个数，木板可以盖住 k 个数。

第二行 n 个数，表示矩阵中的元素。

【输出格式：】

共 n − k + 1 行，每行一个正整数。

第 i 行表示第 i ∼ i + k − 1 个数中最大值是多少。

[算法分析：]

这道题是可以用st表做区间RMQ的，但也可以用单调队列.

st表复杂度为预处理的\(O(n log_2 n)\)，

而单调队列的复杂度为\(O(n)\)（有一些省略掉的常数）

使用双端队列容器\(deque\)便于维护序列的单调性，

由于是每次输出最大值，所以从队尾将所有小于要加入元素\(a\)的值都\(pop\)掉，再把a push_back()进去

现在考虑如何取出多余的队首：

比如已经开始找区间\([3,\ 5]\)的最值了，第二个元素就是多余的

使用一个结构体存储元素的数值和位置，如果这个元素的位置加上\(k\)比当前的\(i\)还要小，则pop_front()

\([Code:]\)

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN = 2e6 + 1;

int n, k;

int a[MAXN];

struct Node {

	int v, pos;

};

deque<Node> q;

inline int read() {

	int x=0, f=1; char ch=getchar();

	while(ch<'0' || ch>'9') {

		if(ch == '-') f = -1;

		ch = getchar();

	}

	while(ch>='0' && ch<='9')

		x=(x<<3)+(x<<1)+ch-48, ch=getchar();

	return x * f;

}

int main() {

	n = read(), k = read();

	for(int i=1; i<=n; ++i) a[i] = read();

    //先将前k个元素加入队列

	for(int i=1; i<=k; ++i) {

		while(!q.empty() && q.back().v < a[i]) q.pop_back();

		q.push_back((Node){a[i], i});

	}

	printf("%d\n", q.front().v);

	for(int i=k+1; i<=n; ++i) {

		while(!q.empty() && q.back().v < a[i]) q.pop_back();

		q.push_back((Node){a[i], i});

		while(q.front().pos + k <= i) q.pop_front();

		printf("%d\n", q.front().v);

	}

}

巴特西

【洛谷】【单调队列】P2032 扫描

最新文章

热门文章