Posted on 2010-07-15 21:02
Uriel 閱讀(818)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
ECUST OJ
原題地址：
http://www.cn210.com/onlinejudge/problemshow.php?pro_id=181 期末考試的將近1個(gè)月時(shí)間都沒(méi)怎么做題，手很生，個(gè)人賽極其挫。。
這道是暑假集訓(xùn)個(gè)人賽第二場(chǎng)最后一題，比賽當(dāng)時(shí)沒(méi)人出。
題意很好懂就不重復(fù)了，那么大的數(shù)據(jù)，暴搜顯然不行。因?yàn)樽詈笄笥卸嗌倥Ｈ汉妥畲蟮呐Ｈ河卸嗌僦慌＃苋菀紫氲讲⒉榧１荣惍?dāng)時(shí)我也就只想到了這么多，光用并查集不加別的優(yōu)化肯定還是TLE的，所以就放棄了。
比賽完看了解題報(bào)告知道了要用AVL實(shí)現(xiàn)查找，刪除操作，因?yàn)閿?shù)據(jù)結(jié)構(gòu)講過(guò)，自己也看過(guò)，于是YY了很久，被左旋右旋繞暈了都沒(méi)出sample，今天問(wèn)了大牛們才知道STL有個(gè)很神奇的set，查找之類的操作都可以O(shè)(lgn)，于是又YY了很久總算AC了。。
參考的解題報(bào)告
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;
}