Description

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

Input

第一行为 \(3\) 个整数, 分别表示 \(a, b, n\) 的值第二行至第 \(a + 1\) 行每行为 \(b\) 个非负整数, 表示矩阵中相应位置上的数. 每行相邻两数之间用一空格分隔.

Output

仅一个整数, 为 \(a \times b\) 矩阵中所有 “\(n \times n\) 正方形区域中的最大整数和 最小整数的差值”“的最小值.

Sample Input

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

Sample Output

1

Data Range

对于 100% 的数据, 2 a, b 1000, n a, n b, n 100 $

Explanation

可以用类似 DP 的方法来解这道题, 就是先维护每一行上一段区间的最大值和最小值, 然后 再接着维护一个矩阵内的最大值和最小值. 与求和不一样, 求和具有连续性, 而这个没有. 我们可以考虑建 \(2n\) 颗线段树来维护这些数据, 然后每一次查询, 但是实际并不需要这样 麻烦. 只需要用一个类似单调队列 (支持弹出) 的 STL 容器就可以了.

然后就可以水过这道题了, 时间复杂度 \(O(a \cdot b \cdot \log (a \cdot b))\), 空间 复杂度 \(O(a \cdot b)\), 并且取决于 STL 的空间复杂度实现.

又一次 1A 好开心~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 1010;
const int infinit = 0x7f7f7f7f;

int a, b, n;
int arr[maxn][maxn];
int dp_row[maxn][maxn][2], // max, min [sub-rows]
    dp_col[maxn][maxn][2]; // max, min [matrices]

void decrement(map<int, int>& _map, int val) {
    _map[val]--; if (_map[val] <= 0)
    _map.erase(_map.find(val)); return ; }
void increment(map<int, int>& _map, int val) {
    _map[val]++; return ; }
int min_in(map<int, int>& _map) {
    map<int, int>::iterator itert = _map.begin();
    return itert->first; }
int max_in(map<int, int>& _map) {
    map<int, int>::iterator itert = _map.end();
    itert--; return itert->first; }

int main(int argc, char** argv)
{
    scanf("%d%d%d", &a, &b, &n);
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            scanf("%d", &arr[i][j]);
    // Processing maximum & minimum values on each row
    for (int i = 1; i <= a; i++) {
        map<int, int> mp;
        increment(mp, 0); // Fail-safe (easier-to-code tweak) addition
        for (int j = 1; j <= n - 1; j++)
            increment(mp, arr[i][j]);
        for (int j = 1; j + n - 1 <= b; j++) {
            // Shift forward, by one position
            decrement(mp, arr[i][j - 1]);
            increment(mp, arr[i][j + n - 1]);
            // Update max, minimum values
            dp_row[i][j][0] = max_in(mp);
            dp_row[i][j][1] = min_in(mp);
        }
    }
    // Processing maximum & minimum values through columns (therefore matrices)
    for (int j = 1; j + n - 1 <= b; j++) {
        map<int, int> mp[2];
        range(0,1) increment(mp[_], 0); // Fail-safe (easier-to-code tweak) additionb
        for (int i = 1; i <= n - 1; i++)
            range(0,1) increment(mp[_], dp_row[i][j][_]);
        for (int i = 1; i + n - 1 <= a; i++) {
            // Shift forward, by one position
            range(0,1) decrement(mp[_], dp_row[i - 1][j][_]),
                       increment(mp[_], dp_row[i + n - 1][j][_]);
            // Update max, minimum values
            dp_col[i][j][0] = max_in(mp[0]);
            dp_col[i][j][1] = min_in(mp[1]);
        }
    }
    int best_diff = infinit;
    for (int i = 1; i + n - 1 <= a; i++)
        for (int j = 1; j + n - 1 <= b; j++)
            best_diff = min(best_diff, dp_col[i][j][0] - dp_col[i][j][1]);
    printf("%d\n", best_diff);
    return 0;
}