HAOI 2007 理想的正方形
本文正體字版由OpenCC轉換
[算法一]
可以看作一個區間固定的二維RMQ，方法爲四分正方形，把正方形兩個方向橫切兩刀，動態規劃解決。其實思想的本質就是ST算法的二維擴展。
時間複雜度爲O(ABLogN)，會稍有超時。
[算法二]
用單調隊列把先按正方形邊長，把每個正方形壓縮成一行。然後對壓縮後的每一行再用單調隊列求出每個正方形的最大值和最小值。
時間複雜度爲O(AB+N^2)。
算法一
/*
* Problem: HAOI2007 square
* Author: Guo Jiabao
* Time: 2009.4.1 22:00
* State: Solved
* Memo: 二維RMQ Sparse Table
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,MAXS=101,LG=6,INF=0x7FFFFFFF;
using namespace std;
int N,M,P,Ans;
int F[MAXN][MAXN][LG],G[MAXN][MAXN][LG];
void init()
{
int i,j;
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
scanf("%d%d%d",&N,&M,&P);
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
{
scanf("%d",&F[i][j][0]);
G[i][j][0]=F[i][j][0];
}
Ans=INF;
}
inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}
void SparseTable()
{
int i1,i2,j,jt,max,min;
for (j=jt=1;jt<=P;j++,jt=jt<<1)
{
for (i1=1;i1+jt<=N;i1++)
{
for (i2=1;i2+jt<=M;i2++)
{
max=0;min=INF;
max=Max(max,F[i1][i2][j-1]);
max=Max(max,F[i1][i2+jt][j-1]);
max=Max(max,F[i1+jt][i2][j-1]);
max=Max(max,F[i1+jt][i2+jt][j-1]);
F[i1][i2][j]=max;
min=Min(min,G[i1][i2][j-1]);
min=Min(min,G[i1][i2+jt][j-1]);
min=Min(min,G[i1+jt][i2][j-1]);
min=Min(min,G[i1+jt][i2+jt][j-1]);
G[i1][i2][j]=min;
}
}
}
}
int Log2(int a)
{
int r;
for (r=0;(1<<r)<=a;r++);
return r-1;
}
void solve()
{
int i,j,k,kt,min,max;
k=Log2(P);
kt=1<<k;
for (i=1;i+P-1<=N;i++)
{
for (j=1;j+P-1<=M;j++)
{
max=0;min=INF;
max=Max(max,F[i][j][k]);
max=Max(max,F[i][j+P-kt][k]);
max=Max(max,F[i+P-kt][j][k]);
max=Max(max,F[i+P-kt][j+P-kt][k]);
min=Min(min,G[i][j][k]);
min=Min(min,G[i][j+P-kt][k]);
min=Min(min,G[i+P-kt][j][k]);
min=Min(min,G[i+P-kt][j+P-kt][k]);
Ans=Min(Ans,max-min);
}
}
}
int main()
{
init();
SparseTable();
solve();
printf("%dn",Ans);
return 0;
}
算法二
/*
* Problem: HAOI2007 square
* Author: Guo Jiabao
* Time: 2009.4.2 14:16
* State: Solved
* Memo: 單調隊列
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001;
using namespace std;
struct element
{
int i,p;
};
struct minmonoqueue
{
element Q[MAXN];
int Width,head,tail;
void ins(int i,int p)
{
while (tail>=head && (i-Q[tail].i>=Width || p<=Q[tail].p))
tail--;
Q[++tail].p=p;
Q[tail].i=i;
}
int get(int i)
{
while (i-Q[head].i>=Width)
head++;
return Q[head].p;
}
void init(int W)
{
Width=W;
head=0;tail=-1;
}
}MinQ;
struct maxmonoqueue
{
element Q[MAXN];
int Width,head,tail;
void ins(int i,int p)
{
while (tail>=head && (i-Q[tail].i>=Width || p>=Q[tail].p))
tail--;
Q[++tail].p=p;
Q[tail].i=i;
}
int get(int i)
{
while (i-Q[head].i>=Width)
head++;
return Q[head].p;
}
void init(int W)
{
Width=W;
head=0;tail=-1;
}
}MaxQ;
int N,M,P,Ans;
int A[MAXN][MAXN],B[MAXN][MAXN],C[MAXN][MAXN];
void init()
{
int i,j;
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
scanf("%d%d%d",&N,&M,&P);
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
scanf("%d",&A[i][j]);
Ans=0x7FFFFFFF;
}
void solve()
{
int i,j,k,Amin,Amax;
for (j=1;j<=M;j++)
{
MinQ.init(P);
MaxQ.init(P);
for (i=1;i<P;i++)
{
MinQ.ins(i,A[i][j]);
MaxQ.ins(i,A[i][j]);
}
for (i=P;i<=N;i++)
{
MinQ.ins(i,A[i][j]);
MaxQ.ins(i,A[i][j]);
k=i-P+1;
B[k][j]=MinQ.get(i);
C[k][j]=MaxQ.get(i);
}
}
for (i=1;i+P-1<=N;i++)
{
MinQ.init(P);
MaxQ.init(P);
for (j=1;j<P;j++)
{
MinQ.ins(j,B[i][j]);
MaxQ.ins(j,C[i][j]);
}
for (j=P;j<=M;j++)
{
MinQ.ins(j,B[i][j]);
MaxQ.ins(j,C[i][j]);
Amin=MinQ.get(j);
Amax=MaxQ.get(j);
if (Amax-Amin<Ans)
Ans=Amax-Amin;
}
}
}
int main()
{
init();
solve();
printf("%d\n",Ans);
return 0;
}
<strong>【問題描述】</strong>
有一個a*b的整數組成的矩陣，現請你從中找出一個n*n的正方形區域，使得該區域所有數中的最大值和最小值的差最小。
<strong>【輸入】</strong>:
第一行爲3個整數，分別表示a,b,n的值
第二行至第a+1行每行爲b個非負整數，表示矩陣中相應位置上的數。每行相鄰兩數之間用一空格分隔。
<strong>【輸出】</strong>:
僅一個整數，爲a*b矩陣中所有“n*n正方形區域中的最大整數和最小整數的差值”的最小值。
<strong>【輸入輸出樣例1】</strong>
square.in
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
square.out
1
<strong>【數據範圍】</strong>
（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
上次修改時間 2017-02-03