bzoj1604[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居*

逃离我推掉我的手 2021-12-24 19:39 284阅读 0赞

[bzoj1604\[Usaco2008 Open\]Cow Neighborhoods 奶牛的邻居][bzoj1604_Usaco2008 Open_Cow Neighborhoods]

题意：

n只牛，牛结成群当且仅当两只牛曼哈顿距离≤c或存在第三头牛使两头牛与它的曼哈顿距离都≤c，求最大的群和群数。n≤100000

题解：

好神啊。先把曼哈顿距离转成切比雪夫距离，(x,y)转为(x+y,x-y)。然后按x坐标排序，用两个指针维护使x坐标差值≤c，同时将新插入的y坐标放入set，每次在set里查找出与当前y差值不超过c的最大y，将这两个点合并成一个集合，用并查集维护。

代码：

1 #include <cstdio>
     2 #include <cstring>
     3 #include <algorithm>
     4 #include <set>
     5 #define inc(i,j,k) for(int i=j;i<=k;i++)
     6 #define maxn 100100
     7 #define INF 0x3fffffff
     8 using namespace std;
     9 
    10 inline int read(){
    11     char ch=getchar(); int f=1,x=0;
    12     while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1; ch=getchar();}
    13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    14     return f*x;
    15 }
    16 struct p{
        int x,y;}; p ps[maxn];
    17 bool cmp(p a,p b){
        return a.x==b.x?a.y<b.y:a.x<b.x;}
    18 struct data{
    19     int id,v;
    20     bool operator < (const data &a)const{
        return v==a.v?id<a.id:v<a.v;}
    21 };
    22 set<data> s; int n,c,l,fa[maxn],cnt[maxn];
    23 int find(int x){
        return x==fa[x]?x:fa[x]=find(fa[x]);}
    24 void merge(int _x,int _y){
        int x=find(_x),y=find(_y); if(x!=y)fa[y]=x;}
    25 int main(){
    26     n=read(),c=read(); inc(i,1,n){
        int a=read(),b=read(); ps[i]=(p){a+b,a-b};} sort(ps+1,ps+1+n,cmp);
    27     s.clear(); s.insert((data){
        0,INF}); s.insert((data){
        0,-INF});
    28     l=1; s.insert((data){
        1,ps[1].y}); inc(i,1,n)fa[i]=i;
    29     inc(i,2,n){
    30         while(ps[i].x-ps[l].x>c)s.erase(s.find((data){l,ps[l].y})),l++;
    31         set<data>::iterator x=s.lower_bound((data){
        0,ps[i].y}),y=x; y--;
    32         if(x->v-ps[i].y<=c)merge(i,x->id); if(ps[i].y-y->v<=c)merge(i,y->id);
    33         s.insert((data){i,ps[i].y});
    34     }
    35     inc(i,1,n)cnt[find(i)]++; int ans=0; inc(i,1,n)if(cnt[i])ans++; printf("%d ",ans);
    36     ans=0; inc(i,1,n)ans=max(ans,cnt[i]); printf("%d",ans); return 0;
    37 }

20160809

转载于:https://www.cnblogs.com/YuanZiming/p/5769007.html

[bzoj1604_Usaco2008 Open_Cow Neighborhoods]: http://www.lydsy.com/JudgeOnline/problem.php?id=1604