题意:给定n行m列的矩阵,每个格子是一个有权值的小方块.将矩阵分成两个部分,要求每个部分内部的方块之间，可以通过上下左右相互到达，而且每个内部的方块之间互相到达，最多允许拐一次弯,使得两个部分的极差的较大值 最小.(n,m<=2000.)
分析:"最大值最小"不难想到要二分答案,直接二分两个部分的极差的较大值为(mid),然后(check)时就是构建一个合法的部分,然后判断另一部分是否合法.
为了保证答案最优,显然矩阵的最大值(maxn)和最小值(minn),要分别在两个部分,至于具体在哪个部分就需要我们枚举了,这里的枚举实际上就是每次翻转矩阵90度,然后去二分答案,连续完成四次,就遍历到了所有的情况.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=2005;
int n,m,minn=1e9,maxn;
int a[N][N];
inline bool check(int mid){
int p=m;
for(int i=1;i<=n;++i){
int t=0;
for(int j=1;j<=p;++j){
if(maxn-a[i][j]<=mid)t=max(t,j);//构建一部分
else break;
}
for(int j=t+1;j<=m;++j)
if(a[i][j]-minn>mid)return false;//判断另一部分
p=t;
}
return true;
}
inline int erfen(){
int l=0,r=maxn-minn,ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
a[i][j]=read();
minn=min(minn,a[i][j]);//最小值
maxn=max(maxn,a[i][j]);//最大值
}
int ans=maxn-minn;//答案上限
ans=min(ans,erfen());
for(int i=1;i<=n;i++)for(int j=1;j<=m/2;j++)swap(a[i][j],a[i][m-j+1]);//翻转矩阵
ans=min(ans,erfen());
for(int i=1;i<=n/2;i++)for(int j=1;j<=m;j++)swap(a[i][j],a[n-i+1][j]);
ans=min(ans,erfen());
for(int i=1;i<=n;i++)for(int j=1;j<=m/2;j++)swap(a[i][j],a[i][m-j+1]);
ans=min(ans,erfen());
printf("%d
",ans);
return 0;
}