阅读原文 给定 \(H \times W\) 的网格，每个小格（ \(1 \times 1\) 的网格）都有一个权值。 现在要将其分为两部分，一个为阶梯型（从上往下每行长度单调递增）、另一个为倒阶梯型（从下往上每行长度单调递增）。请合理地划分这个网格使得两边极差（该部分最大值 \(-\) 最小值）较大的一个最小。输出较大的极差。 注意关键词。“较大的一个最小” \(\rightarrow\) “最大值最小”！ 二分答案，出来吧！ 显然，我们二分那个较大的极差，二分左边界是 \(0\) ，右边界是全局最大值 \(maxn\) 与全局最小值 \(minn\) 的差。那么 \(check()\) 函数怎么写呢？ 假设当前二分到的答案是 \(mid\) 。显然我们可以钦定全局最大值在左边一部分，全局最小值在右边一部分。那么将所有符合 \(mid\) 极差（即 \(maxn-x \leqslant mid\) ）的数 \(x\) 全都分到左边，注意保留倒阶梯型（左边部分每行的长度依次递减）；而右边的数 \(x\) 只要不符合 \(mid\) 极差（即 \(x-minn \leqslant mid\) ）答案就显然不成立。 当然，钦定全局最大值在左边一部分，全局最小值在右边一部分的答案不一定是最优的。我们还应当将原图 \(90^\circ\) 旋转 \(3\) 次分别按上面的步骤解答一次，更新答案。 整个过程就是这样，如果还没明白或者觉得需要证明的，评论区见！感谢您的耐心阅读！ 代码如下：
#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } const int inf=1<<30; int h,w,a[2005][2005],maxn=-inf,minn=inf,ans=inf; inline void turn1() { for(register int i=1;i<=h;i++) for(register int j=1;j<=w/2;j++) swap(a[i][j],a[i][w-j+1]); } inline void turn2() { for(register int i=1;i<=h/2;i++) for(register int j=1;j<=w;j++) swap(a[i][j],a[h-i+1][j]); } inline bool ck(int mid) { int r=w; for(register int i=1;i<=h;i++) { int rm=0; for(register int j=1;j<=r;j++) { if(maxn-a[i][j]<=mid) rm=max(rm,j); else break; } r=rm; for(register int j=rm+1;j<=w;j++) if(mid<a[i][j]-minn) return 0; } return 1; } inline int work() { int l=0,r=maxn-minn; while(l<r) { int mid=(l+r)/2; if(ck(mid)) r=mid; else l=mid+1; } return l; } int main() { h=read(); w=read(); for(register int i=1;i<=h;i++) { for(register int j=1;j<=w;j++) { a[i][j]=read(); maxn=max(maxn,a[i][j]); minn=min(minn,a[i][j]); } } ans=min(ans,work()); turn1(); ans=min(ans,work()); turn2(); ans=min(ans,work()); turn1(); ans=min(ans,work()); printf("%d\n",ans); return 0; }转载于:https://www.cnblogs.com/Peter0701/p/11574636.html
相关资源：JAVA上百实例源码以及开源项目