[ABC330F] Minimize Bounding Square

[ABC330F] Minimize Bounding Square

博导yth给的题目。

考虑到直接O(n)不太好做，但确定了正方形的边长之后可以很方便地计算操作次数，所以我们直接二分正方形的边长。

现在转化成 \(n\) 个点用边长为 \(s\) 的正方形框起来最小的代价。

将 \(x\) 和 \(y\) 分开考虑，假设我们要算 \(x\) 的代价。

设当前最大值为 \(max\)，最小值为 \(min\)。

• 如果最大值减最小值都要小于s的话，不用操作，退出
• 否则，正方形放在两个最值之间最优，代价为 \(max\) – \(min\) – \(s\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,x[N],y[N];
long long k;
int check(int s)
{
    int cnt=0;
    long long ans=0;
    while(n-cnt*2>1)
    {
        cnt++;
        if(x[n-cnt+1]-x[cnt]<s)break;
        ans+=x[n-cnt+1]-x[cnt]-s;
    }
    cnt=0;
    while(n-cnt*2>1)
    {
        cnt++;
        if(y[n-cnt+1]-y[cnt]<s)break;
        ans+=y[n-cnt+1]-y[cnt]-s;
    }
    return ans<=k;
}
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
    sort(x+1,x+1+n),sort(y+1,y+1+n);
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}