$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=0,y=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*y; } const int N=510; int n,c,as,b[N*2],ct,sum[N*2][N*2]; struct node{int x,y;}a[510]; il bool ck(int qvq) { if(qvq>=b[ct])return 1; Rg int ovo=upper_bound(b+1,b+ct+1,b[ct]-qvq+1)-b-1; go(i,1,ovo) go(j,1,ovo) { Rg int x=upper_bound(b+1,b+ct+1,b[i]+qvq-1)-b-1,y=upper_bound(b+1,b+ct+1,b[j]+qvq-1)-b-1; if(sum[x][y]-sum[i-1][y]-sum[x][j-1]+sum[i-1][j-1]>=c)return 1; } return 0; } int main() { c=read(),n=read(); go(i,1,n)a[i].x=read(),a[i].y=read(),b[++ct]=a[i].x,b[++ct]=a[i].y; sort(b+1,b+ct+1);ct=unique(b+1,b+ct+1)-(b+1);b[++ct]=10001; go(i,1,n) { Rg int x=lower_bound(b+1,b+ct+1,a[i].x)-b,y=lower_bound(b+1,b+ct+1,a[i].y)-b; sum[x][y]++; } go(i,1,ct)go(j,1,ct)sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; Rg int l=1,r=10010,mid; while(l<=r) { mid=(l+r)>>1; if(ck(mid))as=mid,r=mid-1; else l=mid+1; } printf("%d ",as); return 0; }