Description

众所周知，小Z拥有者足以毁灭世界的力量，可惜他不能控制这份力量，小J和小Z的关系十分亲密，一天小J预感到了小Z体内的力量将要爆发。
这次爆发的力量比以往都要强大，以至于将小Z分为了两个整体，彼此之间靠着万有引力互相靠近，一旦融合，世界将不复存在。
为了拯救世界，小J决定打造一个容器G，将小Z的两个部分分别装在容器G的一个部分，用以控制小Z
容器由n*m个魔法水晶组成，他们组成了一个n行m列的矩阵，每个魔法水晶都有自己的能量值，容器需要
被分为两个部分，使得每个魔法水晶都属于且仅属于一个部分，并且任何一个魔法水晶都可以在矩阵中只经过和自己属于同一部分的魔法水晶由一条最多改变一次方向的路径抵达另一个和他处于同一部分的魔法水晶
例如：
ＡＡＡＡＡ. .ＡＡＡＡＡ. .ＡＡＡＡＡ
ＡＡＢＡＡ. .ＢＡＡＡＡ. .ＡＡＡＢＢ
ＡＢＢＢＡ. .ＢＢＡＡＡ. .ＡＡＡＢＢ
ＡＡＢＡＡ. .ＢＡＡＡＡ. .ＡＢＢＢＢ
ＡＡＡＡＡ. .ＡＡＡＡＡ. .ＢＢＢＢＢ

…(1)…(2)…(3)…
使用.隔开（辣鸡的题面格式化）
其中12是不合法的容器，3是合法的容器
对于每一个部分，他的不稳定性是属于这个部分的所有魔法水晶能量值的极差（最大-最小）
对于整个容器，不稳定性是两部分不稳定性中的最大值
为了知道自己能不能拯救世界，不白白浪费时间，小J想知道整个容器的最小的不稳定值

Input

第一行两个数n，m代表魔法水晶组成的矩阵大小
随后n行，每行m个整数表示魔法水晶的能量值

Output

一行一个整数，表示最小的不稳定值

Sample Input

4 4
1 12 6 11
11 4 2 14
10 1 9 20
4 17 13 10

Sample Output

11

样例说明
ＢＢＢＡ
ＢＢＢＡ
ＢＢＢＡ
ＢＡＡＡ
B极差12-1=11 A极差20-10=10，不稳定值为11，分法不唯一

Data Constraint

对于15%的数据 n，m≤10
对于另15%的数据，n，m中有一个为1
对于55%的数据 n，m≤200（包括最初的15%）
对于所有数据，n，m≤2000，1≤能量值≤1e9

Solution

• 首先要发现分成的两部分一定是一个阶梯状。

• 设矩阵中最大值为 $mx$ 、最小值为 $mn$。

• 那答案最大也就是 $mx-mn$ ，如果更小的话，那么就将会是 $mx$ 在一部分， $mn$ 在另一部分。

• 这里只考虑令阶梯型从左下到右上（将原矩形旋转90°，转四次处理取最小值即可）的情况。

• 我们强制令 $mx$ 在左上部分、$mn$ 在右下部分（没有也没关系，反正转四次总会有的）。

• 再二分答案 $mid$ ，那么每一行从左开始的值都会有一个限制（即值不能小于 $mx-mid$）。

• 这个我们可以对每一行做一个前缀最小值，二分出那个位置 $pos$ 即可。

• 之后我们就要判断 $pos$ 之后的值是否也满足条件（即值不能超过 $mn+mid$）。

• 这个我们可以对每一行做一个后缀最大值，直接判断即可。

• 时间复杂度就是 $O(4(nm+nlo{g}^{2}n))$ 。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int N=2005,inf=1e9; int n,m,ans=inf,mn=inf,mx; int a[N][N],b[N][N]; int pre[N][N],suf[N][N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline bool check(int x) {int last=m+1;for(int i=1;i<=n;i++){int l=0,r=m,pos=0;while(l<=r){int mid=l+r>>1;if(mx-pre[i][mid]<=x){l=mid+1;pos=mid;}else r=mid-1;}last=min(last,pos);if(suf[i][last+1]-mn>x) return false;}return true; } inline void work() {for(int i=1;i<=n;i++){pre[i][0]=inf;for(int j=1;j<=m;j++) pre[i][j]=min(pre[i][j-1],a[i][j]);suf[i][m+1]=0;for(int j=m;j;j--) suf[i][j]=max(suf[i][j+1],a[i][j]);}int l=0,r=mx-mn,val=r;while(l<=r){int mid=l+r>>1;if(check(mid)){r=mid-1;val=mid;}else l=mid+1;}ans=min(ans,val); } int main() {freopen("separate.in","r",stdin);freopen("separate.out","w",stdout);n=read(),m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){a[i][j]=read();mn=min(mn,a[i][j]);mx=max(mx,a[i][j]);}work();for(int i=2;i<=4;i++){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) b[j][n-i+1]=a[i][j];memcpy(a,b,sizeof(a));swap(n,m);work();}printf("%d",ans);return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 5938. 【NOIP2018模拟10.30】分离计划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。