[BZOJ 1047][HAOI 2007] 理想的正方形

题目大意

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

\(2 \leqslant n \leqslant a, b \leqslant 1,000\)

题目链接

BZOJ 1047

CodeVS 1715

题解

单调队列暴力乱搞。。。

先横向算出一个 \(a \times (b - n + 1)\) 的矩阵,每一个值表示以此点开始 \(n\) 个数中的最大值,在对该矩阵纵向做一遍,最后得到一个 \((a - n + 1) \times (b - n + 1)\) 的矩阵,每一个指表示以此点为左上角的 \(n \times n\) 的矩阵中的最大值;对最小值做同样的事情,最后直接比较一遍即可。

单调队列:像普通队列一样进出,但调用 top() 函数时会返回队列中的最大/小值,具体实现可以参考其他神犇们的博客或我的代码。

代码

一开始很逗比地以为最后的矩阵是 \((a - n) \times (b - n)\) 的。。。举个 \(n = 1\) 的例子后发现我傻了。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
// #define DBG
const int MAXN = 1005;
template <bool isMax>
struct MonotoneQueue {
std::deque<int> q, m;
void push(int x) {
q.push_back(x);
if (isMax) while (!m.empty() && m.back() < x) m.pop_back();
else while (!m.empty() && m.back() > x) m.pop_back();
m.push_back(x);
}
int top() {
return m.front();
}
void pop() {
int x = q.front();
q.pop_front();
if (x == m.front()) m.pop_front();
}
};
int m1[MAXN][MAXN], m2[MAXN][MAXN], mMax[MAXN][MAXN], mMin[MAXN][MAXN];
int main() {
int a, b, n;
scanf("%d %d %d", &a, &b, &n);
for (int i = 1; i <= a; i++) for (int j = 1; j <= b; j++) scanf("%d", &m1[i][j]);
for (int i = 1; i <= a; i++) {
MonotoneQueue<true> q;
for (int j = 1; j <= n; j++) q.push(m1[i][j]);
m2[i][1] = q.top();
for (int j = n + 1; j <= b; j++) {
q.pop();
q.push(m1[i][j]);
m2[i][j - n + 1] = q.top();
}
}
for (int i = 1; i <= b - n + 1; i++) {
MonotoneQueue<true> q;
for (int j = 1; j <= n; j++) q.push(m2[j][i]);
mMax[1][i] = q.top();
for (int j = n + 1; j <= a; j++) {
q.pop();
q.push(m2[j][i]);
mMax[j - n + 1][i] = q.top();
}
}
for (int i = 1; i <= a; i++) {
MonotoneQueue<false> q;
for (int j = 1; j <= n; j++) q.push(m1[i][j]);
m2[i][1] = q.top();
for (int j = n + 1; j <= b; j++) {
q.pop();
q.push(m1[i][j]);
m2[i][j - n + 1] = q.top();
}
}
for (int i = 1; i <= b - n + 1; i++) {
MonotoneQueue<false> q;
for (int j = 1; j <= n; j++) q.push(m2[j][i]);
mMin[1][i] = q.top();
for (int j = n + 1; j <= a; j++) {
q.pop();
q.push(m2[j][i]);
mMin[j - n + 1][i] = q.top();
}
}
a -= n - 1, b -= n - 1;
#ifdef DBG
puts("mMax:");
for (int i = 1; i <= a; i++) for (int j = 1; j <= b; j++)
printf("%d%c", mMax[i][j], j == b ? '\n' : ' ');
puts("mMin:");
for (int i = 1; i <= a; i++) for (int j = 1; j <= b; j++)
printf("%d%c", mMin[i][j], j == b ? '\n' : ' ');
#endif
int ans = INT_MAX;
for (int i = 1; i <= a; i++) for (int j = 1; j <= b; j++)
ans = std::min(ans, mMax[i][j] - mMin[i][j]);
printf("%d\n", ans);
return 0;
}