题意

Farmer John wishes to build a corral for his cows. Being finicky beasts, they demand that the corral be square and that the corral contain at least C (1 <= C <= 500) clover fields for afternoon treats. The corral‘s edges must be parallel to the X,Y axes.

FJ‘s land contains a total of N (C <= N <= 500) clover fields, each a block of size 1 x 1 and located at with its lower left corner at integer X and Y coordinates each in the range 1..10,000. Sometimes more than one clover field grows at the same location; such a field would have its location appear twice (or more) in the input. A corral surrounds a clover field if the field is entirely located inside the corral‘s borders.

Help FJ by telling him the side length of the smallest square containing C clover fields.

分析

参照evenbao的题解。

首先，我们发现答案是具有单调性的，也就是说，如果边长为C的正方形可以，那么比边长C大的正方形也可以，因此，可以二分答案

那么，我们怎么检验呢？

每个点的坐标最大时达到10000，因此，直接二维前缀和显然是会超时的

考虑将坐标离散化，然后求二维前缀和，由于N<=500，所以离散化后最多也只有1000个点

检验时，我们枚举正方形的左上角，用二分求出它的右下角，然后，判断正方形内是否有大于C的草量

时间复杂度\(O(N^2 \log N)\)

代码

#include<iostream>
#include<algorithm>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;
    rg char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x){
    return x=read<T>();
}
typedef long long ll;
using namespace std;

struct data{
    int x,y;
}a[501];
int c,n,tot;
int rec[1002][1002],b[1002];
void discrete(){
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=n;++i)
        ++rec[lower_bound(b+1,b+tot+1,a[i].x)-b][lower_bound(b+1,b+tot+1,a[i].y)-b];
    b[++tot]=10001;
    for(int i=1;i<=tot;++i)
        for(int j=1;j<=tot;++j)
            rec[i][j]+=rec[i-1][j]+rec[i][j-1]-rec[i-1][j-1];
}
bool valid(int cur){
    if(cur>=b[tot]) return 1;
    int p=upper_bound(b+1,b+tot+1,b[tot]-cur+1)-b-1;
    for(int i=1;i<=p;++i)
        for(int j=1;j<=p;++j){
            int tx=upper_bound(b+1,b+tot+1,b[i]+cur-1)-b-1,
                ty=upper_bound(b+1,b+tot+1,b[j]+cur-1)-b-1;
            if(rec[tx][ty]-rec[i-1][ty]-rec[tx][j-1]+rec[i-1][j-1]>=c) return 1;
        }
    return 0;
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(c),read(n);
    for(int i=1;i<=n;++i)
        b[++tot]=read(a[i].x),b[++tot]=read(a[i].y);
    discrete();
    int l=1,r=10000;
    while(l<r){
        int mid=(l+r)>>1;
        if(valid(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}

再分析

lydrainbowcat有一份类似滑动窗口的代码，每次找覆盖C的最短区间，时间复杂度\(O(N^2)\)。

左闭右开区间，前缀和base 1，这波操作简直天秀。

再代码

#include<iostream>
#include<algorithm>
#include<vector>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;
    rg char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x){
    return x=read<T>();
}
typedef long long ll;
using namespace std;

vector<int> X,Y;
co int maxn=501,INF=0x7fffffff;
int sum[maxn][maxn];
vector<pair<int,int> > p;
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int C=read<int>(),n=read<int>(),x,y;
    for(int i=1;i<=n;++i){
        int a=read<int>(),b=read<int>();
        p.push_back(make_pair(a,b));
        X.push_back(a);
        Y.push_back(b);
    }
    sort(p.begin(),p.end());
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    sort(Y.begin(),Y.end());
    Y.erase(unique(Y.begin(),Y.end()),Y.end());
    x=X.size(),y=Y.size();
    X.push_back(INF),Y.push_back(INF);
    int pos=0;
    for(int i=1;i<=x;++i) // base 1
        for(int j=1;j<=y;++j){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            while(pos<n&&p[pos].first==X[i-1]&&p[pos].second==Y[j-1])
                ++sum[i][j],++pos;
        }
    int ans=INF;
    for(int i=0;i<x;++i){ // [i,i1) & [j,j1)
        int i1=i+1,s=0,j=0,j1=1;
        int val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j];
        while(1){
            while(val<C&&(i1<x||j1<y)){
                s=min(X[i1]-X[i],Y[j1]-Y[j]);
                while(X[i1]-X[i]<=s) ++i1;
                while(Y[j1]-Y[j]<=s) ++j1;
                val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j];
            }
            if(val<C) break;
            ans=min(ans,s+1);
            ++j;
            if(j==y) break;
            if(j1<=j) j1=j+1,s=0;
            else s-=Y[j]-Y[j-1];
            while(X[i1-1]-X[i]>s) --i1;
            val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j];
        }
    }
    printf("%d\n",ans);
    return 0;
}

POJ3179 Corral the Cows

原文：https://www.cnblogs.com/autoint/p/10392602.html