P2216 [HAOI2007]理想的正方形 方法記錄

• 2022 年 10 月 11 日
• 筆記

[HAOI2007]理想的正方形

題目描述

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

輸入格式

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

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

輸出格式

僅一個整數，為 \(a \times b\) 矩陣中所有「 \(n \times n\) 正方形區域中的最大整數和最小整數的差值」的最小值。

樣例 #1

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

提示

問題規模。

矩陣中的所有數都不超過 \(1,000,000,000\)。

\(20\%\) 的數據 \(2 \le a,b \le 100,n \le a,n \le b,n \le 10\)。

\(100\%\) 的數據 \(2 \le a,b \le 1000,n \le a,n \le b,n \le 100\)。

題解

前置知識

試想一下，如果我們把\(a*b\)的矩陣改為長度為\(a\)的序列，要找的東西變成長度為\(n\)的子段，那不就變成單調隊列之滑動窗口了嘛。

可以先看看我寫的這篇關於滑動窗口的部落格。

有了這些對單調隊列的基本認知，我們不難想出一種本題的做法。

方法分析

首先可以將\(a*b\)的矩陣理解為\(b\)行長度為\(a\)的序列，然後對每一行的序列使用「滑動窗口」，這樣就可以處理出每一行中長度為\(n\)的子段中所有數的最大值和最小值。

我們用\(board[i][j]\)來存原來的矩陣，用\(x1[i][j]\)和\(x2[i][j]\)分別記錄第\(i\)行第\(j\)個窗口的最小值和最大值。那麼我們每一行就能產生\(b-n+1\)個窗口。處理出來的\(x1\)和\(x2\)規模就是\(a*(b-n+1)\).

for(int i=1;i<=a;i++)
	{
		int h=0,t=0;
		memset(q1,0,sizeof(q1));
		memset(q2,0,sizeof(q2));
		for(int j=1;j<=b;j++)
		{
			while(h<=t&&j-q1[h]>=n) h++;
			while(h<=t&&board[i][j]<board[i][q1[t]]) t--;
			q1[++t]=j;
			if(j>=n) x1[i][j-n+1]=board[i][q1[h]];
		}
		for(int j=1;j<=b;j++)
		{
			while(h<=t&&j-q2[h]>=n) h++;
			while(h<=t&&board[i][j]>board[i][q2[t]]) t--;
			q2[++t]=j;
			if(j>=n) x2[i][j-n+1]=board[i][q2[h]];
		}
	}

然後我們在處理好的\(x1\)和\(x2\)基礎上，對每一列使用「滑動窗口」。如果說每一行的滑動窗口是從左往右滑動的，那麼每一列的滑動窗口就是從上往下滑動的。

我們用用\(y1[i][j]\)和\(y2[i][j]\)分別記錄第\(i\)列第\(j\)個窗口的最小值和最大值。那麼我們每一列就能產生\(a-n+1\)個窗口。處理出來的\(y1\)和\(y2\)規模就是\((a-n+1)*(b-n+1)\).

for(int i=1;i<=b-n+1;i++)
	{
		int h=0,t=0;
		memset(q1,0,sizeof(q1));
		memset(q2,0,sizeof(q2));
		for(int j=1;j<=a;j++)
		{
			while(h<=t&&j-q1[h]>=n) h++;
			while(h<=t&&x1[j][i]<x1[q1[t]][i]) t--;
			q1[++t]=j;
			if(j>=n) y1[j-n+1][i]=x1[q1[h]][i];
		}
		for(int j=1;j<=a;j++)
		{
			while(h<=t&&j-q2[h]>=n) h++;
			while(h<=t&&x2[j][i]>x2[q2[t]][i]) t--;
			q2[++t]=j;
			if(j>=n) y2[j-n+1][i]=x2[q2[h]][i];
		}
	}

回想一下，\(x\)數組處理出的是每一行長度為\(n\)的子段中最小/最大值，\(y\)數組處理出的是\(x\)的基礎上每一列長度為\(n\)的子段中最小/最大值，那麼這樣一來\(y\)數組中就是整個矩陣中\(n*n\)的正方形區域中的最小/最大值。

然後只需要遍歷一遍，求出最小的\(y2[i][j]-y1[i][j]\)即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1005;
int a,b,n;
int board[N][N];
int x1[N][N],x2[N][N],y1[N][N],y2[N][N];
int q1[N],q2[N];
int cntx1,cntx2,cnty1,cnty2;
int minn(int a,int b)
{
	return a<b?a:b;
}
int ans=2147483647;
int main()
{
	scanf("%d%d%d",&a,&b,&n);
	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++)
			scanf("%d",&board[i][j]);
	for(int i=1;i<=a;i++)
	{
		int h=0,t=0;
		memset(q1,0,sizeof(q1));
		memset(q2,0,sizeof(q2));
		for(int j=1;j<=b;j++)
		{
			while(h<=t&&j-q1[h]>=n) h++;
			while(h<=t&&board[i][j]<board[i][q1[t]]) t--;
			q1[++t]=j;
			if(j>=n) x1[i][j-n+1]=board[i][q1[h]];
		}
		for(int j=1;j<=b;j++)
		{
			while(h<=t&&j-q2[h]>=n) h++;
			while(h<=t&&board[i][j]>board[i][q2[t]]) t--;
			q2[++t]=j;
			if(j>=n) x2[i][j-n+1]=board[i][q2[h]];
		}
	}
	memset(q1,0,sizeof(q1));
	memset(q2,0,sizeof(q2));
	for(int i=1;i<=b-n+1;i++)
	{
		int h=0,t=0;
		memset(q1,0,sizeof(q1));
		memset(q2,0,sizeof(q2));
		for(int j=1;j<=a;j++)
		{
			while(h<=t&&j-q1[h]>=n) h++;
			while(h<=t&&x1[j][i]<x1[q1[t]][i]) t--;
			q1[++t]=j;
			if(j>=n) y1[j-n+1][i]=x1[q1[h]][i];
		}
		for(int j=1;j<=a;j++)
		{
			while(h<=t&&j-q2[h]>=n) h++;
			while(h<=t&&x2[j][i]>x2[q2[t]][i]) t--;
			q2[++t]=j;
			if(j>=n) y2[j-n+1][i]=x2[q2[h]][i];
		}
	}
	for(int i=1;i<=a-n+1;i++)
		for(int j=1;j<=b-n+1;j++)
			ans=minn(ans,y2[i][j]-y1[i][j]);
	printf("%d\n",ans);
	return 0;
}