Posted on 2010-07-15 21:02
Uriel 阅读(794)
评论(2) 编辑 收藏 引用 所属分类:
ECUST OJ
原题地址：
http://www.cn210.com/onlinejudge/problemshow.php?pro_id=181 期末考试的将近1个月时间都没怎么做题，手很生，个人赛极其挫。。
这道是暑假集训个人赛第二场最后一题，比赛当时没人出。
题意很好懂就不重复了，那么大的数据，暴搜显然不行。因为最后求有多少牛群和最大的牛群有多少只牛，很容易想到并查集。比赛当时我也就只想到了这么多，光用并查集不加别的优化肯定还是TLE的，所以就放弃了。
比赛完看了解题报告知道了要用AVL实现查找，删除操作，因为数据结构讲过，自己也看过，于是YY了很久，被左旋右旋绕晕了都没出sample，今天问了大牛们才知道STL有个很神奇的set，查找之类的操作都可以O(lgn)，于是又YY了很久总算AC了。。
参考的解题报告
http://blog.imzzl.com/2010/05/406.html 我的丑陋的代码：
#include<set>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct point
{
int x,y,index;
friend bool operator<(const point &a,const point &b)
{
if(a.y==b.y)return a.x<b.x;
return a.y<b.y;
}
};
point p[100050];
int cnt[100050],n,c,father[100050];
set<point>SET;
set<point>::iterator it1,it2;
bool cmp(point a,point b)
{
return a.x<b.x;
}
int find(int x)
{
if(father[x]==x)return x;
else
return father[x]=find(father[x]);
}
void Union(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx>fy)father[fx]=fy;
else
father[fy]=fx;
}
void Sov()
{
int i,j,maxx,h,zzl;
SET.insert(p[1]);
h=1;
for(i=2;i<=n;i++)
{
while((p[i].x-p[h].x)>c)
{
SET.erase(p[h]);
h++;
}
SET.insert(p[i]);
it1=it2=SET.find(p[i]);
it1--;
it2++;
if(it1!=SET.end() && abs((it1)->y-p[i].y)<=c)
{
Union(i,it1->index);
}
if(it2!=SET.end() && abs((it2)->y-p[i].y)<=c)
{
Union(it2->index,i);
}
}
zzl=0;
for(i=1;i<=n;i++)
{
if(father[i]==i)zzl++;
cnt[find(i)]++;
}
maxx=0;
for(i=1;i<=n;i++)
{
if(cnt[i]>maxx)maxx=cnt[i];
}
printf("%d %d\n",zzl,maxx);
return ;
}
int main()
{
int i,x,y;
scanf("%d %d",&n,&c);
for(i=1;i<=n;i++)
{
scanf("%d %d",&x,&y);
p[i].x=x+y;p[i].y=x-y;
father[i]=i;
cnt[i]=0;
}
sort(p+1,p+n+1,cmp);
for(i=1;i<=n;i++)p[i].index=i;
Sov();
return 0;
}