赶牛入圈

Tag: 二分 离散化 二维前缀和

思路

题意很简洁，求二维平面内，由C个点组成的正方形的最小边长。

可以发现，边长增大时，可以纳入的点增多，即-答案与要求线性相关。可以二分

由于点数值大，而数量较小，需离散化

同时为了更快计算由$[lx,ly]$ ~ $[rx,ry]$ 之间的点，所以我们需要使用二维前缀和进行高效计算值

Code1

#include<bits/stdc++.h>
using namespace std;
map<int,int>mpx,mpy;
map<int,int>xmp,ymp;
int n,c,x[512],y[512];
int a[512][512];
set<int>sx,sy;
int idx,idy;
int getbox(int r1, int c1, int r2, int c2) {
    if (r1 > r2 || c1 > c2) return 0;
    return a[r2][c2] - a[r1 - 1][c2] - a[r2][c1 - 1] + a[r1 - 1][c1 - 1];
}
int check(int len)
{
  int sum=0;
  for(int lx=1,rx=1;lx<=idx;lx++)
  {
    for(int ly=1,ry=1;ly<=idy;ly++)
    {
      while( rx<idx && xmp[rx+1]-xmp[lx]<=len ) rx++;
      while( ry<idy && ymp[ry+1]-ymp[ly]<=len ) ry++;
      sum=max(sum,getbox( lx,ly,rx,ry ));
    }
  }
  return sum;
}
int main()
{
  cin>>c>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>x[i]>>y[i];
    sx.insert(x[i]);
    sy.insert(y[i]);
  }
  for( auto x:sx )
  {
    idx++;
    mpx[x]=idx;
    xmp[idx]=x;
  }
  for( auto y:sy )
  {
    idy++;
    mpy[y]=idy;
    ymp[idy]=y;
  }
  for(int i=1;i<=n;i++)
  {
    a[ mpx[x[i]] ][ mpy[ y[i]] ]++;
  }
    for (int i = 1; i <= idx; i++) {
        for (int j = 1; j <= idy; j++) {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
  int l=0,r=10012;
  while(l<=r)
  {
    int mid=l+r>>1;
    if( check(mid)>=c ) r=mid-1;
    else l=mid+1;
  }
  cout<<l+1;
}

Code2

#include<bits/stdc++.h>
using namespace std;
map<int,int>mpx,mpy;
map<int,int>xmp,ymp;
int n,c,x[512],y[512];
int a[512][512];
set<int>sx,sy;
int idx,idy;
int getbox(int r1, int c1, int r2, int c2) {
    if (r1 > r2 || c1 > c2) return 0;
    return a[r2][c2] - a[r1 - 1][c2] - a[r2][c1 - 1] + a[r1 - 1][c1 - 1];
}
int check(int len)
{
  int sum=0;
  for( auto [lx,idlx] : mpx )
  {
    for( auto [ly,idly] : mpy )
    {

      auto rx=sx.lower_bound( lx+len );
      if( rx==sx.end() || *rx>lx+len )  rx--;
      auto ry=sy.lower_bound( ly+len );
      if( ry==sy.end() || *ry>ly+len )  ry--;

      sum=max( sum,getbox(idlx,idly,mpx[*rx],mpy[*ry]) );
    }
  }
  return sum;
}
int main()
{
  cin>>c>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>x[i]>>y[i];
    sx.insert(x[i]);
    sy.insert(y[i]);
  }
  for( auto x:sx )
  {
    idx++;
    mpx[x]=idx;
    xmp[idx]=x;
  }
  for( auto y:sy )
  {
    idy++;
    mpy[y]=idy;
    ymp[idy]=y;
  }
  for(int i=1;i<=n;i++)
  {
    a[ mpx[x[i]] ][ mpy[ y[i]] ]++;
  }
    for (int i = 1; i <= idx; i++) {
        for (int j = 1; j <= idy; j++) {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
  int l=0,r=10012;
  while(l<=r)
  {
    int mid=l+r>>1;
    if( check(mid)>=c ) r=mid-1;
    else l=mid+1;
  }
  cout<<l+1;
}