题目链接：P2216 [HAOI2007]理想的正方形
题目描述
有一个 $a\times b$的整数组成的矩阵，现请你从中找出一个 $n\times n$的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入格式
第一行为3个整数，分别表示a,b,n的值
第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
输出格式
仅一个整数，为 $a\times b$矩阵中所有“ $n\times n$正方形区域中的最大整数和最小整数的差值”的最小值。
输入输出样例
输入 #1
1
2
3
4
5
6
| 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
（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
思路
单调队列
二维 RMQ 问题。
设原矩阵为 m[][]，用单调队列求每行的最大/最小值，分别存入两个矩阵 maxr[][] 和 minr[][]。maxr[i][j] 代表 m[i][j] 到 m[i][j + n - 1] 的最大值，minr[i][j] 代表 m[i][j] 到 m[i][j + n - 1] 的最小值。
接下来对这两个矩阵用单调队列求每列的最大/最小值，分别存入两个矩阵 maxc[][] 和 minc[][]。maxr[i][j] 代表 m[i][j] 到 m[i + n - 1][j + n - 1] 的最大值，minr[i][j] 代表 m[i][j] 到 m[i + n - 1][j + n - 1] 的最小值。
最后遍历 maxc[][] 和 minc[][] 即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int m[maxn][maxn];
int maxr[maxn][maxn], maxc[maxn][maxn];
int minr[maxn][maxn], minc[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int a, b, n;
cin >> a >> b >> n;
for(int i = 1; i <= a; ++i) {
for(int j = 1; j <= b; ++j) {
cin >> m[i][j];
}
}
for(int i = 1; i <= a; ++i) {
int l = 1, r = 1;
int L = 1, R = 1;
int q1[maxn] = {0, l}, q2[maxn] = {0, L};
for(int j = 2; j <= b; ++j) {
while(r >= l && j - q1[l] >= n) ++l;
while(r >= l && m[i][j] <= m[i][q1[r]]) --r;
q1[++r] = j;
if(j >= n) minr[i][j - n + 1] = m[i][q1[l]];
while(R >= L && j - q2[L] >= n) ++L;
while(R >= L && m[i][j] >= m[i][q2[R]]) --R;
q2[++R] = j;
if(j >= n) maxr[i][j - n + 1] = m[i][q2[L]];
}
}
for(int i = 1; i <= b - n + 1; ++i) {
int l = 1, r = 1;
int L = 1, R = 1;
int q1[maxn] = {0, l}, q2[maxn] = {0, L};
for(int j = 2; j <= a; ++j) {
while(r >= l && j - q1[l] >= n) ++l;
while(r >= l && minr[j][i] <= minr[q1[r]][i]) --r;
q1[++r] = j;
if(j >= n) minc[j - n + 1][i] = minr[q1[l]][i];
while(R >= L && j - q2[L] >= n) ++L;
while(R >= L && maxr[j][i] >= maxr[q2[R]][i]) --R;
q2[++R] = j;
if(j >= n) maxc[j - n + 1][i] = maxr[q2[L]][i];
}
}
int ans = inf;
for(int i = 1; i <= a - n + 1; ++i) {
for(int j = 1; j <= b - n + 1; ++j) {
ans = min(ans, maxc[i][j] - minc[i][j]);
}
}
cout << ans << endl;
return 0;
}
|