$Poj3179\ Corral\ the\ Cows$ 二分+离散化+二维前缀和

Poj

$Description$

在一个二维平面上,有$N$颗草,每颗草的大小是$1*1$,左下角坐标为$x_i,y_i$.要求一个正方形,正方形的边平行于$x$或$y$轴,正方形里面包含至少$C$颗草.求正方形的最小边长.注意,同一个区域可能生长多颗草.

数组范围:$1<=N,C<=500\ 1<=x_i,y_i<=10000$

$Sol$

最简单暴力的方法当然就是枚举正方形的一个顶点,就定为左上顶点叭,然后再从小到大枚举边长,然后$check()$,更新答案.显然这个方法复杂度爆炸$qwq$,而且,$check()$要用到二位前缀和,而根据$x,y$的范围,这根本就存不下.

1.虽然$x,y$的范围很大,但是$N$只有$500$鸭,所以就离散化!

2.发现合法的边长是单调的.如果当前边长可以,那么更大的显然也可以,所以二分就好了.

觉得这里的离散化好妙.jpg

特别要注意$lowerbound()$和$upperbound()$的区别吖!

$Code$

//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<algorithm>

#define il inline

#define Rg register

#define go(i,a,b) for(Rg int i=a;i<=b;++i)

#define yes(i,a,b) for(Rg int i=a;i>=b;--i)

#define mem(a,b) memset(a,b,sizeof(a))

#define ll long long

#define db double

using namespace std;

il int read()

{

    Rg int x=,y=;char c=getchar();

    while(c<''||c>''){if(c=='-')y=-;c=getchar();}

    while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}

    return x*y;

}

const int N=;

int n,c,as,b[N*],ct,sum[N*][N*];

struct node{int x,y;}a[];

il bool ck(int qvq)

{

    if(qvq>=b[ct])return ;

    Rg int ovo=upper_bound(b+,b+ct+,b[ct]-qvq+)-b-;

    go(i,,ovo)

        go(j,,ovo)

    {

        Rg int x=upper_bound(b+,b+ct+,b[i]+qvq-)-b-,y=upper_bound(b+,b+ct+,b[j]+qvq-)-b-;

        if(sum[x][y]-sum[i-][y]-sum[x][j-]+sum[i-][j-]>=c)return ;

    }

    return ;

}

int main()

{

    c=read(),n=read();

    go(i,,n)a[i].x=read(),a[i].y=read(),b[++ct]=a[i].x,b[++ct]=a[i].y;

    sort(b+,b+ct+);ct=unique(b+,b+ct+)-(b+);b[++ct]=;

    go(i,,n)

    {

        Rg int x=lower_bound(b+,b+ct+,a[i].x)-b,y=lower_bound(b+,b+ct+,a[i].y)-b;

        sum[x][y]++;

    }

    go(i,,ct)go(j,,ct)sum[i][j]+=sum[i-][j]+sum[i][j-]-sum[i-][j-];

    Rg int l=,r=,mid;

    while(l<=r)

    {

        mid=(l+r)>>;

        if(ck(mid))as=mid,r=mid-;

        else l=mid+;

    }

    printf("%d\n",as);

    return ;

}

巴特西

$Poj3179\ Corral\ the\ Cows$ 二分+离散化+二维前缀和

最新文章

热门文章