Thomasguo666的小屋

首先我们简化一下题意。题目的意思是说，让我们找一个包含 $\lceil \frac{n^2}{2} \rceil $ 个点的连通块的相邻格之间高度差的最大值的最小值。

诸如这种最小化 max 值的题目，常见思路是使用二分答案将其由最优化问题转为可行性问题。

具体到这道题，我们二分高度差的最大值，设最大值为 mid。然后我们可以把把 $n^2$ 个格子对应成 $n^2$ 个点，把整张网格当作一张无向图。两个节点之间有边，当且仅当这两个节点所对应的格子相邻，且高度之差不超过 mid。

那么接下来我们可以发现，问题转化为：求出一张 $n^2$ 阶图中是否存在至少有 $\lceil \frac{n^2}{2} \rceil $ 个点的联通块。这里我们使用并查集即可快速地解决该问题。具体地说，对于图中的每一条边，若其两端点不在同一连通块，则我们将其右端点的连通块和左端点的连通块合并。若新连通块包含了过半数的点，则判定为存在。若对所有边进行了上述操作后，仍未判定为存在，则判定为不存在。

更多实现的细节问题，见代码：

#include <bits/stdc++.h>
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define in inline
#define re register
using namespace std;
typedef long long ll;
typedef double db;
in int read()
{
    int ans=0,f=1;char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) ans=(ans<<3)+(ans<<1)+(c^48);
    return ans*f;
}
in int cmin(int &a,int b) {return a=min(a,b);}
in int cmax(int &a,int b) {return a=max(a,b);}
int n;
int a[505][505];
int dx[]={1,0};
int dy[]={0,1};
int st[500005],en[500005];
int fa[250005],sz[250005],tot;
in int zip(int x,int y) // 将点 (x,y) 压缩成一个 [1,n*n] 之间的整数
{
    return (x-1)*n+y;
}
int find(int x) // 并查集寻根函数
{
    return x==fa[x]?x:fa[x]=find(fa[x]); // 路径压缩
}
int check(int mid) // 二分答案的判断函数
{
    tot=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            fa[zip(i,j)]=zip(i,j);
            sz[zip(i,j)]=1;
            for (int k=0;k<2;k++)
            {
                int ii=i+dx[k],jj=j+dy[k];
                if (ii<=n && jj<=n && abs(a[i][j]-a[ii][jj])<=mid) // 只有符合要求的才连边
                {
                    st[++tot]=zip(i,j);
                    en[tot]=zip(ii,jj);
                }
            }
        }
    }
    for (int i=1;i<=tot;i++)
    {
        int u=st[i],v=en[i];
        int uu=find(u),vv=find(v);
        if (uu==vv) continue;
        fa[vv]=uu;
        sz[uu]+=sz[vv]; // 合并集合
        sz[vv]=0;
    }
    for (int i=1;i<=n*n;i++)
    {
        if (sz[i]*2>=n*n) return 1;
    }
    return 0;
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=read();
    int l=0,r=1000000,ans=1000000;
    while (l<=r) // 二分答案
    {
        int mid=l+r>>1;
        if (check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}