肯定是二分答案了, 枚举最大的极差, 带入到最大值所在的区域内, 区域分好后再判断是否满足
可以证明分好的区域边缘必然是一个楼梯样的, 高度递减的 (我觉得不用证明吧)
而且每个区域必定会占一个角,
而且最大和最小的肯定不能在同一个区域, 否则还玩啥啊
如果我们从最大值所在的区域来看的话
可能会分别在不同的角上
而在不同的角判断的方法不一样
因为写好几种判断太麻烦了
所以直接存把矩阵旋转 90.180.270 度的情况一起存下来
相当于默认角在某一个位置, 这样就可以用一种判断的方法就可以把所有情况都判断完了
不过存储的写法很是巧妙啊
看代码吧
- #include<bits/stdc++.h>
- using namespace std;
- inline int read(){
- char ch=getchar();
- int res=0;
- while(!isdigit(ch)) ch=getchar();
- while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
- return res;
- }
- int n,m,a[4][2005][2005],gmax=-2e9-1,gmin=2e9+1,endi[2005];
- inline bool check(int u,int k)
- {
- if(u&1) swap(m,n);
- endi[0]=m;
- for(int i=1,j;i<=n;i++)
- {
- for(j=1;j<=endi[i-1];j++)
- {
- if(gmax>a[u][i][j]+k)
- break;
- }
- endi[i]=j-1;
- }
- for(int i=1;i<=n;i++)
- {
- for(int j=endi[i]+1;j<=m;j++)
- {
- if(a[u][i][j]>gmin+k)
- {
- if(u&1) swap(m,n);
- return false;
- }
- }
- }
- if(u&1) swap(m,n);
- return true;
- }
- inline bool che(int k)
- {
- for(int i=0;i<4;i++)
- {
- if(check(i,k)) return true;
- }
- return false;
- }
- int main(){
- n=read(),m=read();
- int x=1,x1=1,x2=n,x3=m,y=1,y1=n,y2=m,y3=1,t;
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- t=a[0][x][y++]=a[1][x1++][y1]=a[2][x2][y2--]=a[3][x3--][y3]=read();
- if(t>gmax)gmax=t;
- if(t<gmin) gmin=t;
- }
- x++,y=1;
- y1--,x1=1;
- x2--,y2=m;
- y3++,x3=n;
- }
- int l=0,r=gmax-gmin;
- while(l<r)
- {
- int mid=(l+r)>>1;
- if(che(mid)) r=mid;
- else l=mid+1;
- }
- cout<<l<<endl;
- return 0;
- }
来源: https://www.cnblogs.com/forever-/p/9737430.html