P2216 [HAOI2007]理想的正方形（dp+单调队列优化）

时间：2024-09-03 00:05:32

题目链接：传送门

题目：

题目描述

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

输入输出格式

输入格式：

第一行为3个整数，分别表示a,b,n的值

第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式：

仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

输入输出样例

输入样例#：

输出样例#：

说明

问题规模

（）矩阵中的所有数都不超过1,,,

（）%的数据2<=a,b<=,n<=a,n<=b,n<=

（）%的数据2<=a,b<=,n<=a,n<=b,n<=

思路：

用2*b个单调队列维护：

　　每列长度为n的最大值和最小值；

再用2个单调队列维护：

　　更新到当前行为止，行数为n的最大值的最大值，和最小值的最小值。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + ;

const int INF = 0x3f3f3f3f;

struct Node{

    int val, ind;

    Node(int v = , int i = ) : val(v), ind(i) {}

}querow[MAX_N], quecol[MAX_N][MAX_N], querow2[MAX_N], quecol2[MAX_N][MAX_N];

int a, b, n;

int headrow, tailrow, headcol[MAX_N], tailcol[MAX_N];

int headrow2, tailrow2, headcol2[MAX_N], tailcol2[MAX_N];

int mat[MAX_N][MAX_N];

int main()

{

    cin >> a >> b >> n;

    int ans = INF;

    for (int i = ; i <= a; i++)

        for (int j = ; j <= b; j++)

            scanf("%d", &mat[i][j]);

    for (int i = ; i <= a; i++)

        headcol[i] = , tailcol[i] = , headcol2[i] = , tailcol2[i] = ;

    for (int i = ; i <= a; i++) {

        headrow = headrow2 = ;

        tailrow = tailrow2 = ;

        for (int j = ; j <= b; j++) {

            while (headcol[j] <= tailcol[j] && quecol[j][tailcol[j]].val <= mat[i][j])

                tailcol[j]--;

            quecol[j][++tailcol[j]] = Node(mat[i][j], i);

            while (headcol[j] <= tailcol[j] && quecol[j][headcol[j]].ind <= i-n)

                headcol[j]++;

            Node cur = quecol[j][headcol[j]];

            while (headrow <= tailrow && querow[tailrow].val <= cur.val)

                tailrow--;

            querow[++tailrow] = Node(cur.val, j);

            while (headrow <= tailrow && querow[headrow].ind <= j-n)

                headrow++;

            Node _max = querow[headrow];

            while (headcol2[j] <= tailcol2[j] && quecol2[j][tailcol2[j]].val >= mat[i][j])

                tailcol2[j]--;

            quecol2[j][++tailcol2[j]] = Node(mat[i][j], i);

            while (headcol2[j] <= tailcol2[j] && quecol2[j][headcol2[j]].ind <= i-n)

                headcol2[j]++;

            Node cur2 = quecol2[j][headcol2[j]];

            while (headrow2 <= tailrow2 && querow2[tailrow2].val >= cur2.val)

                tailrow2--;

            querow2[++tailrow2] = Node(cur2.val, j);

            while (headrow2 <= tailrow2 && querow2[headrow2].ind <= j-n)

                headrow2++;

            Node _min = querow2[headrow2];

            if (i >= n && j >= n)

                ans = min(ans, _max.val - _min.val);

        }

    }

    cout << ans << endl;

    return ;

}

相关文章