题解

本题使用二分答案 + 贪心验证求解矩阵分割问题。

算法思路：

1. 二分答案：

   • 答案具有单调性：如果差值 $mid$ 可行，则更大的值也一定可行
   • 二分枚举答案 $mid \in [0, 10^9]$
   • 对于每个 $mid$，检验是否存在合法的分割方案

2. 验证策略（check函数）：

   • 找到矩阵中的最大值位置 $(x, y)$
   • 将矩阵分为两部分：
     • 第一部分：包含最大值的矩形区域（左上角）
     • 第二部分：剩余的 L 形区域
   • 对于第一部分：标记所有满足 $b[x][y] - b[i][j] \leq mid$ 的位置
   • 对于第二部分的每列，贪心地向下扩展，使得差值不超过 $mid$
   • 最后检查未被标记的区域，其最大值和最小值的差是否 $\leq mid$

3. 对称性处理：

   • 矩阵可能有多种分割方式（左上、右上、左下、右下）
   • 通过上下翻转和左右翻转，枚举四种对称情况
   • 只要有一种情况满足条件即可

4. 答案更新：

   • 如果 $mid$ 可行，更新答案并缩小右边界：$R = mid - 1$
   • 否则扩大左边界：$L = mid + 1$

时间复杂度：$O(n \cdot m \cdot \log(10^9))$

#include<bits/stdc++.h>
#define int long long
#define dbg(x){cout<<x;exit(0);}
using namespace std;
const int N=2001,inf=(1ll<<45);
int n,m;
int a[N][N],b[N][N];
bool vis[N][N];
int x,y;
bool check(int mid){
	memset(vis,0,sizeof vis);
	for(int i=1;i<=x;i++){
		for(int j=1;j<=y;j++){
			if(b[x][y]-b[i][j]>mid)return 0;
			vis[i][j]=1;
		}
	}
	int lst=n;
	for(int j=1;j<=m;j++){
		int p;
		if(j<=y)p=x;
		else p=0;
		while(p+1<=n&&p+1<=lst&&b[x][y]-b[p+1][j]<=mid){
			p++;
			vis[p][j]=1;
		}
		lst=p;//lst表示上一个的位置  最高到哪
	}
	int mx=0,mn=inf;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!vis[i][j]){
				mx=max(mx,b[i][j]);
				mn=min(mn,b[i][j]);
			}
		}
	}
	if(mx-mn>mid)return 0;
	return 1;
	
}
bool solve(int mid){
	memcpy(b,a,sizeof a);
	int mx=0;
	x=0;
	y=0;
	int res=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(b[i][j]>mx){
				mx=b[i][j];
				x=i,y=j;
			}
		}
	}
	res|=check(mid);
//	if(res)dbg(0);
	for(int i=1;i<=n/2;i++){//上下
		for(int j=1;j<=m;j++){
			swap(b[i][j],b[n-i+1][j]);
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<b[i][j]<<' ';
//		}
//		cout<<'\n';
//	}
//	dbg(1);
	x=n-x+1;
	res|=check(mid);
//	if(res)dbg(1);

	for(int j=1;j<=m/2;j++){//上下+左右
		for(int i=1;i<=n;i++){
			swap(b[i][j],b[i][m-j+1]);
		}
	}
//	dbg(0);

	y=m-y+1;
	res|=check(mid);
//	if(res)dbg(2);
	for(int i=1;i<=n/2;i++){//左右
		for(int j=1;j<=m;j++){
			swap(b[i][j],b[n-i+1][j]);
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<b[i][j]<<' ';
//		}
//		cout<<'\n';
//	}
//	dbg(1);
	x=n-x+1;
	res|=check(mid);
//	if(res)dbg(3);
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	int L=0,R=1e9,mid,res=1e9;
//	dbg(solve(12));
	while(L<=R){
		mid=(L+R)/2;
		
		if(solve(mid)){
			res=mid;
			R=mid-1;
		}
		else L=mid+1;
//		cout<<mid<<'\n';
	}
	cout<<res;
	return 0;

}