题目描述
The Kingdom of JOIOI is a rectangular grid of H × W cells. In the Kingdom of JOIOI, in order to improve efficiency of administrative institutions, the country will be divided into two regions called “JOI” and “IOI.”
Since we do not want to divide it in a complicated way, the division must satisfy the following conditions:
• Each region must contain at least one cell.
• Each cell must belong to exactly one of two regions.
• For every pair of cells in the JOI region, we can travel from one to the other by passing through cells belonging to the JOI region only. When move from a cell to another cell, the two cells must share an edge.The same is true for the IOI region.
• For each row or column, if we take all the cells in that row or column, the cells belonging to each region must be connected. All the cells in a row or column may belong to the same region.
Each cell has an integer called the altitude. After we divide the country into two regions, it is expected that traveling in each region will be active. But, if the difference of the altitudes of cells are large, traveling between them becomes hard. Therefore, we would like to minimize the maximum of the difference of the altitudes between cells belonging to the same region. In other words, we would like to minimize the larger value of
• the difference between the maximum and the minimum altitudes in the JOI region, and
• the difference between the maximum and the minimum altitudes in the IOI region.
（中文题意概述）
给定一个矩形，内部每个点有点权。将这个矩形分成两个联通的部分，使得每一部分中任意的一对点之间的最简路径至多有一个拐角。求这两个部分极差的最大值。
样例
输入
输出
11说明
For example, in this sample input, we divide the country into two regions as follows. Here, ‘J’ denotes the JOI
region, and ‘I’ denotes the IOI region.
J J J I
J J J I
J J I I
J I I IThe following division does not satisfy the condition because, in the third column from left, cells with ‘I’ are
not connected.
J J I I
J J J I
J J J I
J I I I思路
首先我们很容易想到，矩形的最大值 / 最小值这两个点一定隶属于不同的部分。所以我们可以二分答案，确定每个部分权值的范围，$\Theta (nm)$ 验证答案的可行性。
从别人的博客里盗一张图说明一下：
对于每一行，贪心地讲可以划给最大值那一部分的点划给最大值部分，如果剩下的点都能划给最小值，二分的这个值就是可行的。为了方便我们计算，把原图翻转即可。
时间复杂度 $\Theta (HW\log (Max−Min))$
代码
#include <bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define mid ((l+r)>>1)
#define maxn 2010
int n,m,a[maxn][maxn];
int mx,mn=INT_MAX;
bool check(int fit){
int lim=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++)
if (a[i][j]<mx-fit)
lim=max(lim,j+1);
for (int j=1;j<lim;j++)
if (a[i][j]>mn+fit)
return false;
}
return true;
}
int solve(){
int l=0,r=mx-mn;
while(l<r){
if (check(mid)) r=mid;
else l=mid+1;
}
return l;
}
void flip_l(){
for (int j=1;j<=m;++j)
for (int i=1;i<=n/2;++i)
std::swap(a[n-i+1][j],a[i][j]);
}
void flip_p(){
for (int i=1;i<=n;++i)
for (int j=1;j<=m/2;j++)
std::swap(a[i][m-j+1],a[i][j]);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
scanf("%d",&a[i][j]),
mx=max(mx,a[i][j]),
mn=min(mn,a[i][j]);
int res=solve();
flip_l();
res=min(res,solve());
flip_p();
res=min(res,solve());
flip_l();
res=min(res,solve());
printf("%d\n",res);
return 0;
}