HAOI 2007 理想的正方形
[算法一]
可以看作一个区间固定的二维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