转载

[转载] $AT2444$ 题解

阅读原文
给定 \(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

正文到此结束
本文目录