[算进] 赶牛入圈 题解

Problem

ACwing 题目地址

Solution

低级套路题。

二分边长，二维离散化前缀和预处理，贪心双指针判定即可。

时间复杂度 \(O(n^2 \log n)\)，因为离散化了，\(n<=500\)

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 1007;
int n,C,cnt,ans,m;
int b[N];
int sum[N][N];
struct Point {
    int x,y;
}P[N];
inline int GetArea(int x1,int y1,int x2,int y2) {
    return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
}
bool check(int len) {
    for(int x1=1,x2=1;x1<=m;++x1) {
        while(b[x2]-b[x1]+1<=len && x2<=m) ++x2;
        --x2;
        //printf("  x2 = %d\n",x2);
        for(int y1=1,y2=1;y1<=m;++y1) {
            while(b[y2]-b[y1]+1<=len && y2<=m) ++y2;
            --y2;
            if(GetArea(x1,y1,x2,y2) >= C) return true;
        }
    }
    return false;
}
int main()
{
    C = read(), n = read();
    for(int i=1,x,y;i<=n;++i) {
        x = read(), y = read();
        P[i] = (Point)<%x,y%>;
        b[++cnt] = x, b[++cnt] = y;
    }
    sort(b+1, b+1+cnt);
    m = unique(b+1, b+1+cnt) - b - 1;
    for(int i=1;i<=n;++i) {
        P[i].x = lower_bound(b+1, b+1+m, P[i].x) - b;
        P[i].y = lower_bound(b+1, b+1+m, P[i].y) - b;
        sum[P[i].x][P[i].y]++;
    }
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j)
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
    //printf("test:: %d\n",sum[m][m]);
    ans = -1;
    int l = 0, r = 10000, mid;
    while(l <= r) {
        mid = (l+r)>>1;
        //printf("%d %d %d\n",l,r,mid);
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    printf("%d\n",ans);
    return 0;
}

Summary

套路题，不会做只是不知道这个套路而已 学到的套路：

• N这么小，值域这么大，试试二维离散化