Posted on 2010-07-15 21:02
Uriel 閱讀(818)
評論(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;
}