AtCoder Beginner Contest 215 F题题解

时间:2021-04-10 14:10:34

F - Dist Max 2

什么时候我才能突破\(F\)题的大关...

算了,不说了,看题。

简化题意:给定\(n\)个点的坐标,定义没两个点的距离为\(min(|x_i-x_j|,|y_i-y_j|)\),求所有点对中距离的最大值。其实看到一个最小,一个最大就应该想到二分的...最小值最大或最大值最小,二分答案不是最擅长解决这类问题的吗?但有时候就会想想了,为什么二分答案在这些条件下就十分适用了...考虑最小值最大(或最大值最小),说明有很多方案,每个方案都有对应的最小值,求所有方案的最大值,显然比最大值小的方案肯定都能实现,那这不就满足答案单调性了吗?再看我们二分答案以后,我们给定一个答案,之后只需判定是否合法就行。这样的话我们还需根据给定的答案去构造一种满足答案的方案即可,这可比解决最优化的问题简单多了。

好了,不多时候了,回到这个题,我们二分一个答案后怎么判断答案是否合法,由于是两维的关系,我门先按\(x\)排序消掉一维,比如说我们二分的答案为\(k\),那我们考虑每个点向后找其他的点匹配,对于当前点\(i\),显然只有\(x_i+k\)之后的点才能被统计,我们可以将之后的点放到一个set里面,这样就能快速找到合法的\(x\)中是否有合法的\(y\)了。总复杂度\(O(nlog^2n)\)这个复杂度竟然T了,好吧,二分答案的log大概30多,再加上set,确实可能会T,但我们考虑这个set的操作,实际上我们需要查询的就是一个后缀的最小值和最大值,这里发现可以直接预处理,开心的省去一个log,看这次还过不过!!!

//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define P 1000000007
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=2e5+10;
int n,mn[N],mx[N];
struct wy{int x,y;}a[N]; inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
} inline bool cmp(wy a,wy b) {return a.x<b.x;} inline bool check(int k)
{
int r=1;
rep(i,1,n)//为每个左端点找合适的右端点
{
while(r<=n&&a[r].x-a[i].x<k) ++r;
if(r>n) return false;
if(abs(mn[r]-a[i].y)>=k||abs(mx[r]-a[i].y)>=k) return true;
}
return false;
} int main()
{
//freopen("1.in","r",stdin);
get(n);
rep(i,1,n) get(a[i].x),get(a[i].y);
sort(a+1,a+n+1,cmp);
mn[n+1]=INF*2;mx[n+1]=-INF;
fep(i,n,1) mn[i]=min(mn[i+1],a[i].y),mx[i]=max(mx[i+1],a[i].y);
int l=0,r=INF*2;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
put(l);
return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.