P2216 [HAOI2007]理想的正方形 - 单调队列

题目

题目描述

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

输入格式

第一行为3个整数，分别表示a,b,n的值

第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式

仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例

输入 #1 复制

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

输出 #1 复制

1

说明/提示

问题规模

（1）矩阵中的所有数都不超过1,000,000,000

（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10

（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100

题解

要求出一个方块内的极值，我们不妨维护两次单调队列：

• 第一次：行，单调队列
• 第二次：上面那个单调队列得到的结果按列维护

这样我们就可以达到目的了

图片@ｃｈｉｌｌ（洛谷）:

代码

#include <iostream>

using namespace std;

const int maxn = 1005;

int a, b, n;
struct node { int val, pos; } q[maxn];
int map[maxn][maxn];
int min_val[maxn][maxn], max_val[maxn][maxn];
int min_ans[maxn][maxn], max_ans[maxn][maxn];

int main() {
	cin >> a >> b >> n;
	for (int i = 1; i <= a; i ++)
		for (int j = 1; j <= b; j ++)
			cin >> map[i][j];
	int head = 0, tail = 0;
	// row max
	for (int i = 1; i <= a; i ++) {
		head = 0, tail = 0;
		for (int j = 1; j <= b; j ++) {
			while (head < tail && map[i][j] >= q[tail - 1].val) tail --;
			q[tail ++] = (node) { map[i][j], j };
			while (head < tail && j - q[head].pos + 1 > n) head ++;
			if (j >= n) max_val[i][j - n + 1] = q[head].val; 
		}
	}
	// row min
	for (int i = 1; i <= a; i ++) {
		head = 0, tail = 0;
		for (int j = 1; j <= b; j ++) {
			while (head < tail && map[i][j] <= q[tail - 1].val) tail --;
			q[tail ++] = (node) { map[i][j], j };
			while (head < tail && j - q[head].pos + 1 > n) head ++;
			if (j >= n) min_val[i][j - n + 1] = q[head].val; 
		}
	}

	for (int j = 1; j <= b - n + 1; j ++) {
		head = 0, tail = 0;
		for (int i = 1; i <= a; i ++) {
			while (head < tail && max_val[i][j] >= q[tail - 1].val) tail --;
			q[tail ++] = (node) { max_val[i][j], i };
			while (head < tail && i - q[head].pos + 1 > n) head ++;
			if (i >= n) max_ans[i - n + 1][j] = q[head].val;
		}
	}
	for (int j = 1; j <= b - n + 1; j ++) {
		head = 0, tail = 0;
		for (int i = 1; i <= a; i ++) {
			while (head < tail && min_val[i][j] <= q[tail - 1].val) tail --;
			q[tail ++] = (node) { min_val[i][j], i };
			while (head < tail && i - q[head].pos + 1 > n) head ++;
			if (i >= n) min_ans[i - n + 1][j] = q[head].val;
		}
	}
	
	int ans = 2e9;
	for (int i = 1; i <= a - n + 1; i ++)
		for (int j = 1; j <= b - n + 1; j ++)
			ans = min(ans, max_ans[i][j] - min_ans[i][j]);
	
	cout << ans << endl;
	
	return 0;
}