理想的正方形

Posted on Edited on In

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

数据结构

单调队列首先对每一行维护一个最大值与最小值.然后再对最大值和最小值,维护一个列的最大值最小值.

相当于把原来的一块\(n \times n\)的矩阵缩成了一个最大/小值

代码如下: 

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
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e3 + 66, inf = 1234567891011;

int n, m, lim, lin, ron, res = inf, a[N][N];
int q[N], Q[N];
int rmax[N][N], rmin[N][N], cmax[N][N], cmin[N][N];

signed main()
{
    int i, j, l, r, L, R;
    n = read(), m = read(), lim = read();
    for (i = 1; i <= n; ++ i) for (j = 1; j <= m; ++ j) a[i][j] = read();

    for (i = 1; i <= n; ++ i)
    {
        l = 1, r = 0, memset(q, 0, sizeof q);
        L = 1, R = 0, memset(Q, 0, sizeof Q);
        for (j = 1; j <= m; ++ j)
        {
            while (l <= r && q[l] + lim <= j) ++ l;
            while (l <= r && a[i][q[r]] < a[i][j]) -- r;
            q[++ r] = j;
            if (j >= lim) rmax[i][++ rmax[i][0]] = a[i][q[l]];

            while (L <= R && Q[L] + lim <= j) ++ L;
            while (L <= R && a[i][Q[R]] > a[i][j]) -- R;
            Q[++ R] = j;
            if (j >= lim) rmin[i][++ rmin[i][0]] = a[i][Q[L]];
        }
    }
    lin = m - lim + 1, ron = n - lim + 1;
    for (j = 1; j <= lin; ++ j)
    {
        l = 1, r = 0, memset(q, 0, sizeof q);
        L = 1, R = 0, memset(Q, 0, sizeof Q);
        for (i = 1; i <= n; ++ i)
        {
            while (l <= r && q[l] + lim <= i) ++ l;
            while (l <= r && rmax[q[r]][j] < rmax[i][j]) -- r;
            q[++ r] = i;
            if (i >= lim) cmax[++ cmax[0][j]][j] = rmax[q[l]][j];

            while (L <= R && Q[L] + lim <= i) ++ L;
            while (L <= R && rmin[Q[R]][j] > rmin[i][j]) -- R;
            Q[++ R] = i;
            if (i >= lim) cmin[++ cmin[0][j]][j] = rmin[Q[L]][j];
        }
    }
    for (i = 1; i <= ron; ++ i) for (j = 1; j <= lin; ++ j) res = min(res, cmax[i][j] - cmin[i][j]);
    put(res);

    return 0;
}

后记:

单调队列神仙题!