P2906 [USACO08OPEN]牛的街区Cow Neighborhoods

传送门

曼哈顿距离好像不好直接算，我们可以把牛的坐标转化一下以方便计算距离

(x,y) --> （x+y，x-y）那么距离就可以表示成 $max(\left |x_1-x_2 \right |,\left | y_1-y_2 \right |)$

自己在草稿纸上算一下就知道了，（因为之后我们会按转化后的横坐标排序，所以式子会少一种情况）

（以下横纵坐标均已转化）

所以可以考虑这样一种方案，把牛按横坐标排序

然后考虑总左到右枚举牛加入队列：每次加入一只牛，与队列里的其他牛比较一下纵坐标距离，这样能够保证每只牛都两两匹配过

并且队列保证当前的牛的横坐标与队列内其他牛的横坐标之差不大于C（即与队列最左的牛横坐标之差不大于C）

但是复杂度会爆炸，考虑优化

可以发现，我们匹配时只要找纵坐标大于它的最小的牛和纵坐标小于它的最大的牛，因为如果它能匹配队列的其他牛A，那么那两只牛也一定至少有一只能匹配A

就是在队列里求一个值的前驱后继，那么很容易想到用平衡树 multiset 来维护

可能会有疑问此时的前驱后继是可以和原数相同的（转化后的横纵坐标可能相同），如果强行维护好像很麻烦的样子

但是对于相同的点显然前驱后继至少有一个会考虑到，那么对答案就不会有影响了

然后并查集维护联通块就好了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e5+;

int n,C;

int fa[N],cnt[N];//cnt是当前每个块的大小

inline int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]); }

inline void uni(int x,int y)//并查集合并两个块

{

    int xa=find(x),xb=find(y);

    if(xa==xb) return;

    fa[xa]=xb; cnt[xb]+=cnt[xa]; cnt[xa]=;

}

struct data//存转化后的横纵坐标

{

    int x,y,id;

    data () { x=y=id=; }

    inline bool operator < (const data &tmp) const {//multiset内按纵坐标排序

        return y<tmp.y;

    }

}d[N];

inline bool cmp(const data &a,const data &b){ return a.x<b.x; }//按横坐标排序

int fir;//队列的最左边位置

multiset <data> s;

multiset <data>::iterator it;

void slove()

{

    sort(d+,d+n+,cmp);//排序

    fir=; s.insert(d[]);//第一个直接加进去

    data t; t.y=2e9+; s.insert(t); t.y=-(2e9+); s.insert(t);//防止指针越界

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

    {

        while(d[i].x-d[fir].x>C) s.erase(s.find(d[fir])),fir++;//更新队列

        it=s.lower_bound(d[i]);//找后继

        t=*it; --it;//找前驱

        if(t.y-d[i].y<=C) uni(t.id,d[i].id);//尝试与后继合并

        t=*it;

        if(d[i].y-t.y<=C) uni(t.id,d[i].id);//尝试与前驱合并

        s.insert(d[i]);//别忘了加到multiset里

    }

}

int main()

{

    int a,b;

    n=read(); C=read();

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

    {

        a=read(),b=read();

        d[i].x=a+b; d[i].y=a-b; d[i].id=i;

        fa[i]=i; cnt[i]=;//初始化

    }

    slove();

    int mx=,tot=;//计算块和最大块大小

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

        if(cnt[i])

        {

            mx=max(mx,cnt[i]);

            tot++;

        }

    printf("%d %d",tot,mx);

    return ;

}

巴特西

P2906 [USACO08OPEN]牛的街区Cow Neighborhoods

最新文章

热门文章