Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

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,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

思路很明确，打一张二维ST表。st[i][j][k][2]表示i，j向右下方2^k内最大的数和最小的数，就可以每一次从前四块递推了！时间复杂度O(N^2 log N)就是查询有点蛋疼。但是光是这样是得不全分的只有60，经过了一波骚操作常数优化才能得到80分。

就在我快要弃疗的时候，我瞬间就想起了fread()快速读入优化。然后随便一交……WOC，竟然A了。看来getchar已经跟不上时代了啊。

#include<cstdio>
#include<algorithm>
#include<cmath>
#define MX 0
#define MN 1
using namespace std;
const int maxn = 1e3 + 5;
const int max2 = 12;
int pow2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096};
int st[maxn][maxn][max2][2], dt, k, n, m, mn, tmp, tmp1, tmp2, turn; 
char c;
inline char gc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int & x) {
    x = 0;c = gc();
    while(c > '9' || c < '0') c = gc();
    while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + c - '0', c = gc();
}
void st2d(int n, int m) {
	tmp = log2(k);
    turn = log2(k - 1);
    for(register int k = 1; k <= tmp; ++k)
        for(register int i = 1; i <= m - pow2[k] + 1; ++i)
               for(register int j = 1; j <= n - pow2[k] + 1; ++j) {
                   st[j][i][k][MN] = min(min(st[j][i][k - 1][MN], st[j + pow2[k - 1]][i + pow2[k - 1]][k - 1][MN]), min(st[j + pow2[k - 1]][i][k - 1][MN], st[j][i + pow2[k - 1]][k - 1][MN]));
                   st[j][i][k][MX] = max(max(st[j][i][k - 1][MX], st[j + pow2[k - 1]][i + pow2[k - 1]][k - 1][MX]), max(st[j + pow2[k - 1]][i][k - 1][MX], st[j][i + pow2[k - 1]][k - 1][MX]));
               }
}
int qMX(int x, int y, int n) {
	tmp = pow2[turn];
    tmp1 = max(st[x][y][turn][MX], st[x + n - tmp][y + n - tmp][turn][MX]);
    tmp2 = max(st[x + n - tmp][y][turn][MX], st[x][y + n - tmp][turn][MX]);
    return max(tmp1, tmp2);
}
int qMN(int x, int y, int n) {
	tmp = pow2[turn];
    tmp1 = min(st[x][y][turn][MN], st[x + n - tmp][y + n - tmp][turn][MN]);
    tmp2 = min(st[x + n - tmp][y][turn][MN], st[x][y + n - tmp][turn][MN]);
    return min(tmp1, tmp2);
}
int main() {
    read(n), read(m), read(k);
    mn = 0x7fffffff;
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= m; ++j)
            read(st[i][j][0][MX]), st[i][j][0][MN] = st[i][j][0][MX];
    st2d(n, m);
    for(register int i = 1; i <= n - k + 1; ++i)
        for(register int j = 1; j <= m - k + 1; ++j) {
            dt = qMX(i, j, k) - qMN(i, j, k);
            if(dt < mn) 
                mn = dt;
        }
    printf("%d", mn);
    return 0;
}