P3933 题解

感觉前面的题解要不太简略，要不有冗余，我决定写一个大小适中的小清新题解！ 给定 $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 \degree $ 旋转 $3$ 次分别按上面的步骤解答一次，更新答案。 整个过程就是这样，如果还没明白或者觉得需要证明的，评论区见！感谢您的耐心阅读！ 代码如下： ```cpp #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],minn=inf,maxn=-inf,ans=inf; inline bool ck(int mid) { int f=w+1; for(register int i=1;i<=h;i++) { int t=0; for(register int j=1;j<=min(f,w);j++) { if(maxn-a[i][j]<=mid) t=max(t,j); else break; } f=t; for(register int j=t+1;j<=w;j++) if(a[i][j]-minn>mid) return 0; } return 1; } inline int work() { int l=0,r=maxn-minn+1; while(l<=r) { int mid=(l+r)>>1; if(ck(mid)) r=mid-1; else l=mid+1; } return l; } 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]); } 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; } ```