理想的正方形

https://loj.ac/problem/10182

题目描述

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

思路

  我们可以先想办法把题目简单化，显然我们可以用单调队列一遍扫过去求出以(i)为左端点的连续的(n)个数的最大值和最小值，再考虑在列上思考，类似的，我们可以在求出来的最大和最小值的矩阵内按列(dp)，求出(n)列中的最值，这也可以一遍实现，这样复杂度为(O(ab))

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;

int read()
{
	int res=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
	return res*w;
}

int mp[N][N],f_max[N][N],f_min[N][N],f[N][N];
int q[N];
int main()
{
	int a=read(),b=read(),n=read();
	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++)
			mp[i][j]=read();
	int head=0,tail=0;
	for(int i=1;i<=a;i++)
	{
		head=1,tail=0;
		for(int j=1;j<=b;j++)
		{
			while(head<=tail&&j-q[head]>=n)head++;
			while(head<=tail&&mp[i][q[tail]]>=mp[i][j])tail--;
			q[++tail]=j;
			if(j>=n)f[i][j-n+1]=mp[i][q[head]];
		}
	}
	for(int i=1;i<=b;i++)
	{
		head=1,tail=0;
		for(int j=1;j<=a;j++)
		{
			while(head<=tail&&j-q[head]>=n)head++;
			while(head<=tail&&f[q[tail]][i]>=f[j][i])tail--;
			q[++tail]=j;
			if(j>=n)f_min[j-n+1][i]=f[q[head]][i];
		}
	}
	for(int i=1;i<=a;i++)
	{
		head=1,tail=0;
		for(int j=1;j<=b;j++)
		{
			while(head<=tail&&j-q[head]>=n)head++;
			while(head<=tail&&mp[i][q[tail]]<=mp[i][j])tail--;
			q[++tail]=j;
			if(j>=n)f[i][j-n+1]=mp[i][q[head]];
		}
	}
	for(int i=1;i<=b;i++)
	{
		head=1,tail=0;
		for(int j=1;j<=a;j++)
		{
			while(head<=tail&&j-q[head]>=n)head++;
			while(head<=tail&&f[q[tail]][i]<=f[j][i])tail--;
			q[++tail]=j;
			if(j>=n)f_max[j-n+1][i]=f[q[head]][i];
		}
	}
	int ans=0x7fffffff;
	for(int i=1;i<=a-n+1;i++)
		for(int j=1;j<=b-n+1;j++)
			ans=min(ans,f_max[i][j]-f_min[i][j]);
	printf("%d
",ans);
}