离散化和前缀和以前做过，但是不熟，所以借鉴的lyd的代码(不过好像他也没用二分查找,虽然书上这么写的）不过代码中有一些剪枝和为下一步预处理的的操作可能优化了时间，反正62ms过了。。。
附上代码:
1 1 #include<cstdio> 2 2 #include<algorithm> 3 3 #include<cstring> 4 4 #include<set> 5 5 #include<vector> 6 6 #define INF 1<<30 7 7 using namespace std; 8 8 vector<int> X,Y; 9 9 const int maxn=510; 1010 //typedef point pair<int,int>; 1111 int sum[maxn][maxn]; 1212 vector<pair<int,int> >p; 1313 int main(){ 1414 int C,n,x,y; 1515 int a,b; 1616 scanf("%d%d",&C,&n); 1717 for(int i=1;i<=n;i++){ 1818 scanf("%d%d",&a,&b); 1919 p.push_back(make_pair(a,b)); 2020 X.push_back(a); 2121 Y.push_back(b); 2222 } 2323 //排序 2424 sort(p.begin(),p.end()); 2525 sort(X.begin(),X.end()); 2626 X.erase(unique(X.begin(),X.end()),X.end());//去重 2727 sort(Y.begin(),Y.end()); 2828 Y.erase(unique(X.begin(),X.end()),X.end()); 2929 x=X.size(),y=Y.size(); 3030 X.push_back(INF),Y.push_back(INF); 3131 //求二维前缀和 3232 //sum[i][j]是点X[i-1][j-1]的前缀和 3333 int pos=0; 3434 for(int i=1;i<=x;i++){ 3535 for(int j=1;j<=y;j++){ 3636 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; 3737 while(pos<n&&p[pos].first==X[i-1]&&p[pos].second==Y[j-1]){//判断该点是否有草 3838 sum[i][j]++; 3939 pos++; 4040 } 4141 } 4242 } 4343 //查找 4444 int ans=INF; 4545 for(int i=0;i<x;i++){//枚举起点x坐标 4646 int i1=i+1;//终点x坐标 4747 int s=0;//边长 4848 int j=0;//起点y坐标 4949 int j1=1;//终点y坐标 5050 int val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j]; 5151 while(1){ 5252 while(val<C&&(i1<x||j1<y)){ 5353 s=min(X[i1]-X[i],Y[j1]-Y[j]); 5454 while(X[i1]-X[i]<=s)i1++;//因为sum[i][j]是坐标(x-1,y-1)的前缀和 5555 while(Y[j1]-Y[j]<=s)j1++; 5656 val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j]; 5757 } 5858 if(val<C)break;//剪枝 5959 ans=min(ans,s+1); 6060 j++;//y坐标+1 6161 if(j==y)break;//y坐标枚举到头了,退出循环 6262 if(j1<=j){ 6363 j1=j+1; 6464 s=0; 6565 } 6666 else{ 6767 s-=Y[j]-Y[j-1];//边长也相应的减少 6868 } 6969 while(X[i1-1]-X[i]>s) i1--;//为下一轮计算做准备 7070 val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j]; 7171 } 7272 } 7373 printf("%d\n",ans); 7474 }