HAOI2007理想正方形问题分析与实现

本文将详细解析HAOI2007的理想正方形问题。该问题要求在一个给定的矩阵中找到一个N×N的子矩阵，使得这个子矩阵内的最大值与最小值之差最小。

首先，我们需要预处理每一行中连续N个元素的最大值和最小值，并分别存储在两个二维数组mx和mn中。这一过程可以通过使用单调队列高效地完成。接着，对mx和mn进行类似的处理，这次是在列的方向上，计算每列中连续N个元素的最大值和最小值，结果分别存储在MX和MN中。

最后，遍历所有可能的N×N子矩阵，计算每个子矩阵的最大值（来自MX）与最小值（来自MN）之差，找出这些差值中的最小值即为所求答案。

以下是具体的C++代码实现：

/**
 * Problem: 1047
 * User: geng4512
 * Language: C++
 * Result: Accepted
 * Time: 2284 ms
 * Memory: 20536 kb
 **/
#include 
#define min(a, b) ((a) <(b) ? (a) : (b))
const int MAXN = 1005;
int a, b, n, q[MAXN], mp[MAXN][MAXN], mx[MAXN][MAXN], mn[MAXN][MAXN], MX[MAXN][MAXN], MN[MAXN][MAXN];

int main() {
    scanf("%d%d%d", &a, &b, &n);
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            scanf("%d", &mp[i][j]);

    int l = 0, r = 0;
    for (int j = 1; j <= a; j++) { // 计算mx
        l = 0, r = 0;
        for (int i = 1; i <= b; i++) {
            while (l  mp[j][q[r-1]]) --r;
            while (l             q[r++] = i;
            mx[j][i] = mp[j][q[l]];
        }
    }

    for (int j = 1; j <= a; j++) { // 计算mn
        l = 0, r = 0;
        for (int i = 1; i <= b; i++) {
            while (l             while (l             q[r++] = i;
            mn[j][i] = mp[j][q[l]];
        }
    }

    for (int j = 1; j <= b; j++) { // 计算MX
        l = 0, r = 0;
        for (int i = 1; i <= a; i++) {
            while (l  mx[q[r-1]][j]) --r;
            while (l             q[r++] = i;
            MX[i][j] = mx[q[l]][j];
        }
    }

    for (int j = 1; j <= b; j++) { // 计算MN
        l = 0, r = 0;
        for (int i = 1; i <= a; i++) {
            while (l             while (l             q[r++] = i;
            MN[i][j] = mn[q[l]][j];
        }
    }

    int ans = 0x3f3f3f3f;
    for (int i = n; i <= a; i++)
        for (int j = n; j <= b; j++)
            ans = min(MX[i][j] - MN[i][j], ans);

    printf("%d\n", ans);
    return 0;
}

参考链接：geng4512的博客