傳送門
這個題首先我們發現那條分界線是單調的
并且最大值最小應該是老套路了，二分答案。
二分答案之後就可以貪心了，每一行盡量填，具體可以看我的代碼：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
inline int read(){
int x=;char ch=' ';int f=;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')f=-,ch=getchar();
while(ch>='0'&&ch<='9')x=x*+ch-'0',ch=getchar();
return x*f;
}
int n,m,mx,mn=;
int a[][],now[];
inline bool check(int x){
int cap=m;
memset(now,,sizeof(now));
for(int i=;i<=n;i++){
for(int j=;j<=cap;j++){
if(a[i][j]>=mx-x){
now[i]=j;
}
else{
break;
}
}
cap=min(now[i],cap);
for(int j=m;j>now[i];j--){
if(a[i][j]>mn+x){
return false;
}
}
}
return true;
}
inline int solve(){
int l=,r=mx-mn;
int mid;
while(l<r){
mid=(l+r)>>;
if(check(mid)){
r=mid;
}
else{
l=mid+;
}
}
return l;
}
inline void flip_r(){
for(int i=;i<=(n>>);i++){
for(int j=;j<=m;j++){
swap(a[i][j],a[n-i+][j]);
}
}
}
inline void flip_c(){
for(int i=;i<=n;i++){
for(int j=;j<=(m>>);j++){
swap(a[i][j],a[i][m-j+]);
}
}
}
int main(){
n=read();m=read();
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
a[i][j]=read();
mx=max(mx,a[i][j]);
mn=min(mn,a[i][j]);
}
}
int ans=solve();
flip_c();
ans=min(ans,solve());
flip_r();
ans=min(ans,solve());
flip_c();
ans=min(ans,solve());
printf("%d",ans);
return ;
}