526互联

[HAOI2007]理想的正方形【题解】

发布时间 2023-04-05 16:09:10作者: Phrvth

题目描述

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #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,000,000,000\)。

\(20\%\) 的数据 \(2 \le a,b \le 100,n \le a,n \le b,n \le 10\)。

\(100\%\) 的数据 \(2 \le a,b \le 1000,n \le a,n \le b,n \le 100\)。

浅浅谈一下

就是要找 \(n\times n\) 大小的矩阵

我们进行以下两种操作

  • 每行扫一次单调队列，得出来的矩阵为长度为 \(n\)，宽度为 \(1\) 的链
  • 扫完之后每列扫一次单调队列，得出来的矩阵长度为 \(n\)，宽度为 \(n\) 的矩阵

没了

至于为什么是蓝题，你自己看看代码量把

\(\mathcal{Code}\)

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e3 + 7;

int n, m, k, a[MAXN][MAXN];
int h_x[MAXN][MAXN], h_n[MAXN][MAXN], maxx[MAXN][MAXN], minn[MAXN][MAXN], ans = 1e9 + 7;

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	
	for (int i = 1; i <= n; i++) {
		deque<int> Q;//最大值 
		for (int j = 1; j <= m; j++) {
			while (!Q.empty() && Q.front() < j - k + 1) Q.pop_front();
			while (!Q.empty() && a[i][Q.back()] <= a[i][j]) Q.pop_back();
			Q.push_back(j);
			if (j >= k) h_x[i][j - k + 1] = Q.front(); 
		}
		Q.clear();//最小值 
		for (int j = 1; j <= m; j++) {
			while (!Q.empty() && Q.front() < j - k + 1) Q.pop_front();
			while (!Q.empty() && a[i][Q.back()] >= a[i][j]) Q.pop_back();
			Q.push_back(j);
			if (j >= k) h_n[i][j - k + 1] = Q.front(); 
		}
	}
	
	for (int j = 1; j <= m - k + 1; j++) {
		deque<int> Q;//最大值
		for (int i = 1; i <= n; i++) {
			while (!Q.empty() && Q.front() < i - k + 1) Q.pop_front();
			while (!Q.empty() && a[Q.back()][h_x[Q.back()][j]] <= a[i][h_x[i][j]]) Q.pop_back();
			Q.push_back(i);
			if (i >= k) maxx[i - k + 1][j] = Q.front(); 
		}
		Q.clear();//最小值 
		for (int i = 1; i <= n; i++) {
			while (!Q.empty() && Q.front() < i - k + 1) Q.pop_front();
			while (!Q.empty() && a[Q.back()][h_n[Q.back()][j]] >= a[i][h_n[i][j]]) Q.pop_back();
			Q.push_back(i);
			if (i >= k) minn[i - k + 1][j] = Q.front(); 
		}
	}
	
	for (int i = 1; i <= n - k + 1; i++) 
		for (int j = 1; j <= m - k + 1; j++)
			ans = min(ans, a[maxx[i][j]][h_x[maxx[i][j]][j]] - a[minn[i][j]][h_n[minn[i][j]][j]]);
	
	cout << ans << endl;
	
	return 0; 
}

完结撒花✿✿ヽ(°▽°)ノ✿