題目描述

有一個a*b的整數(shù)組成的矩陣，現(xiàn)請你從中找出一個n*n的正方形區(qū)域，使得該區(qū)域所有數(shù)中的最大值和最小值的差最小。

輸入輸出格式

輸入格式：

?

第一行為3個整數(shù)，分別表示a,b,n的值

第二行至第a+1行每行為b個非負(fù)整數(shù)，表示矩陣中相應(yīng)位置上的數(shù)。每行相鄰兩數(shù)之間用一空格分隔。

?

輸出格式：

?

僅一個整數(shù)，為a*b矩陣中所有“n*n正方形區(qū)域中的最大整數(shù)和最小整數(shù)的差值”的最小值。

?

輸入輸出樣例

輸入樣例#1：
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

說明

問題規(guī)模

（1）矩陣中的所有數(shù)都不超過1,000,000,000

（2）20%的數(shù)據(jù)2<=a,b<=100,n<=a,n<=b,n<=10

（3）100%的數(shù)據(jù)2<=a,b<=1000,n<=a,n<=b,n<=100

/* 就是為了這個題目學(xué)的st表st表能夠維護(hù)數(shù)列的某個地方往后2的整數(shù)次方的極值這個題目用st表來維護(hù)矩陣中某個元素往右下方二次方整數(shù)邊長的矩陣元素的極值然后四塊合并 O1 查詢四塊原理就和ST表一樣了 */#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> using namespace std;int maxx[1001][1001][13]; int minn[1001][1001][13]; int read() {int num = 0;char c = getchar();while(c > '9' || c < '0')c = getchar();while(c <= '9' && c >= '0'){num *= 10;num += c - '0';c = getchar();} return num; }int n,m,k,p; int ans = 0x7fffffff; int main() {n = read();m = read();k = read();for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++)maxx[i][j][0] = minn[i][j][0] = read();p = log(k) / log(2);for(int i = 1;i <= 11;i++){for(int j = 1;j + (1 << i) - 1 <= n;j++)for(int z = 1;z + (1 << i) - 1<= m;z++){maxx[j][z][i] = max(maxx[j][z][i - 1],max(maxx[j][z + (1 << (i - 1))][i - 1],max(maxx[j + (1 << (i - 1))][z + (1 << (i - 1))][i - 1],maxx[j + (1 << (i - 1))][z][i - 1])));minn[j][z][i] = min(minn[j][z][i - 1],min(minn[j][z + (1 << (i - 1))][i - 1],min(minn[j + (1 << (i - 1))][z + (1 << (i - 1))][i - 1],minn[j + (1 << (i - 1))][z][i - 1])));}}for(int x = 1;x + k - 1 <= n;x++)for(int y = 1;y + k - 1 <= m;y++){ans = min(ans,max(maxx[x][y][p],max(maxx[x][y + k - (1 << p)][p],max(maxx[x + k - (1 << p)][y][p],maxx[x + k - (1 << p)][y + k - (1 << p)][p]))) -min(minn[x][y][p],min(minn[x][y + k - (1 << p)][p],min(minn[x + k - (1 << p)][y][p],minn[x + k - (1 << p)][y + k - (1 << p)][p]))));}printf("%d",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/luoyibujue/p/7663500.html

總結(jié)

以上是生活随笔為你收集整理的[HAOI2007]理想的正方形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。