[ABC330F] Minimize Bounding Square 题解

FFTotoro · 2023-11-26 08:18:25 · 题解

看到这种边长最小值，一眼二分。

二分一个边长考虑如何判定；显然 x 和 y 可以分开考虑。以 x 为例，预处理将所有 x 坐标排序，枚举那个正方形的左右边界，其中一种最优方案一定是把左或右边界放在其中一个点上。这样用前缀和与二分可以快速求出最小操作数。最后判断 x 与 y 的最小操作数之和即可。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,k; cin>>n>>k;
  vector<int> x(n),y(n),sx,sy;
  for(int i=0;i<n;i++)cin>>x[i]>>y[i];
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  partial_sum(x.begin(),x.end(),back_inserter(sx)); // 前缀和
  partial_sum(y.begin(),y.end(),back_inserter(sy));
  auto sumx=[&](int l,int r)->int{
    if(r==-1)return 0;
    return sx[r]-(l?sx[l-1]:0);
  }; // 求和
  auto sumy=[&](int l,int r)->int{
    if(r==-1)return 0;
    return sy[r]-(l?sy[l-1]:0);
  };
  auto getx=[&](int l,int r){
    int ll=prev(upper_bound(x.begin(),x.end(),l))-x.begin(),
      rr=lower_bound(x.begin(),x.end(),r)-x.begin();
    return (ll+1)*l-sumx(0,ll)+sumx(rr,n-1)-(n-rr)*r;
  }; // 给定正方形的左右端点求操作数
  auto gety=[&](int l,int r){
    int ll=prev(upper_bound(y.begin(),y.end(),l))-y.begin(),
      rr=lower_bound(y.begin(),y.end(),r)-y.begin();
    return (ll+1)*l-sumy(0,ll)+sumy(rr,n-1)-(n-rr)*r;
  };
  int l=0,r=5e14;
  auto f=[&](int s){
    int cx=1e15,cy=1e15;
    for(int i=0;i<n;i++)
      cx=min({cx,getx(x[i],x[i]+s),getx(x[i]-s,x[i])}),
      cy=min({cy,gety(y[i],y[i]+s),gety(y[i]-s,y[i])});
    return cx+cy;
  }; // 求最小操作数
  while(l<r){
    int m=l+r>>1;
    if(f(m)<=k)r=m;
    else l=m+1;
  } // 二分边长
  cout<<r<<endl;
  return 0;
}