自动搬运

查看原文

来自洛谷，原作者为

	Little_x_starTYJ 愿时光能缓，愿故人不散！ || 众所周知，如果把灯泡放在嘴里，即使你自己一个人也取得出来灯泡。

搬运于2025-08-24 22:52:54，当前版本为作者最后更新于2024-02-28 17:08:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

这道题目我们一看，咦？怎么有点像滑动窗口呢？于是就想到了单调队列。

我们定义一个单调队列，对于每一个数，我们判断队头的数字是否小于等于当前数，如果是，那么当前数一定更优，因为他不仅可以在队列里多待一会且贡献大于等于队头，所以我们循环弹出队头，直到队头大于当前数，然后入队清除过时的元素即可。

由于是二维的，所以需要跑两遍。

CODE：

#include <stdio.h>
#include <string.h>
int a[4001][4001], ans[4001][4001], b[4001][4001], q[2];
inline int read() {
	int f = 1, k = 0;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		k = k * 10 + c - '0';
		c = getchar();
	}
	return f * k;
}
inline void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
	return;
}
int main() {
	int n = read(), m = read();
	int i, j;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			a[i][j] = read();
	int r = read(), s = read();
	int k = n - r + 1, k2 = m - s + 1;
	for (i = 1; i <= n; i++) {
		int hh = 0, tt = -1;
		for (j = 1; j <= m; j++) {
			while (hh <= tt && a[i][q[tt]] <= a[i][j])
				tt--;
			q[++tt] = j;
			while (hh <= tt && q[hh] <= j - s)
				hh++;
			if (j >= s)
				b[i][j - s + 1] = a[i][q[hh]];
		}
		memset(q, 0, sizeof(q));
	}
	for (j = 1; j <= k2; j++) {
		int hh = 0, tt = -1;
		for (i = 1; i <= n; i++) {
			while (hh <= tt && b[q[tt]][j] <= b[i][j])
				tt--;
			q[++tt] = i;
			while (hh <= tt && q[hh] <= i - r)
				hh++;
			if (i >= r)
				ans[i - r + 1][j] = b[q[hh]][j];
		}
		memset(q, 0, sizeof(q));
	}
	for (i = 1; i <= k; i++, puts(""))
		for (j = 1; j <= k2; j++)
			write(ans[i][j]), putchar(' ');
	return 0;
}