POJ3179 Corral the Cows题解

我就是个垃圾……一道水题能写这么长时间……

首先看到题就想到了二维前缀和+二分边长，但地图边长10000，得离散化。

于是这个离散化就把我搞疯了，淦。

这反映出现在基础知识还是不牢固，相当不牢固。

复杂度不会算，淦。（但应该不会超过\(O(C^2\log N)\)

具体看代码吧……

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

struct P{int x,y;}a[505];

int c,n,dx,dy,xx[10005],yy[10005];

int x[505],y[505],s[505][505];

bool check(int k)

{

    for(int i=xx[k];i<=dx;++i)    //如果边长是k，那么从k的不同的数开始找起

        for(int j=yy[k];j<=dy;++j)

        {

            int x0=0,y0=0;

            if(x[i]-k>=0) x0=xx[x[i]-k]; //这里是一个映射原坐标的判断，这样的对应应该是没问题的

            if(y[j]-k>=0) y0=yy[y[j]-k];

            if(s[i][j]-s[x0][j]-s[i][y0]+s[x0][y0]>=c) return 1;

        }

    return 0;

}

int main()

{

    scanf("%d%d",&c,&n);

    for(int i=1;i<=n;++i)

    {

        scanf("%d%d",&a[i].x,&a[i].y);

        xx[a[i].x]++,yy[a[i].y]++;    //这是开了个桶

    }

    for(int i=1;i<=10000;++i)

    {

        if(xx[i]) x[++dx]=i;    //如果这个桶有值，那么就把它扔进一个映射的数组里

        xx[i]=dx;    //可以发现x与xx是互为逆运算的，也就是x[i]表示第i个不同的数是几，

                     //xx[i]表示i这个数是第几个不同的数

        if(yy[i]) y[++dy]=i;

        yy[i]=dy;

    }

    for(int i=1;i<=n;++i) s[xx[a[i].x]][yy[a[i].y]]++; //我们用编号来做前缀和

    for(int i=1;i<=dx;++i)

        for(int j=1;j<=dy;++j)

            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];

    int l=1,r=10000,ans;

    while(l<=r)

    {

        int mid=l+r>>1;

        if(check(mid)) ans=mid,r=mid-1;

        else l=mid+1;

    }

    printf("%d",ans);

    return 0;

}

巴特西

POJ3179 Corral the Cows题解

最新文章

热门文章