gyro永不抽风

ああああああああああああああああおおおおおおおおおおおおおおおお

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

题解

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

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

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

图片@chill(洛谷):

代码

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
#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;
}
__EOF__
-------------本文结束感谢您的阅读-------------

本文标题:P2216 [HAOI2007]理想的正方形 - 单调队列

文章作者:gyro永不抽风

发布时间:2020年09月21日 - 23:09

最后更新:2020年09月21日 - 23:09

原始链接:http://gyrojeff.moe/2020/09/21/P2216-HAOI2007-%E7%90%86%E6%83%B3%E7%9A%84%E6%AD%A3%E6%96%B9%E5%BD%A2-%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 转载请保留原文链接及作者!

真的不买杯奶茶吗?T^T

欢迎关注我的其它发布渠道