「BZOJ1604」[Usaco2008 Open] Cow Neighborhoods 奶牛的邻居
Description
了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：
1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi – xil+IYi – Yil≤C.
2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群．
给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛
Input
第1行输入N和C，之后N行每行输入一只奶牛的坐标．
Output
仅一行，先输出牛群数，再输出最大牛群里的牛数，用空格隔开．
Sample Input
4 2
1 1
3 3
2 2
10 10* Line 1: A single line with a two space-separated integers: the
number of cow neighborhoods and the size of the largest cow
neighborhood.
1 1
3 3
2 2
10 10* Line 1: A single line with a two space-separated integers: the
number of cow neighborhoods and the size of the largest cow
neighborhood.
Sample Output
2 3OUTPUT DETAILS:
There are 2 neighborhoods, one formed by the first three cows and
the other being the last cow. The largest neighborhood therefore
has size 3.
There are 2 neighborhoods, one formed by the first three cows and
the other being the last cow. The largest neighborhood therefore
has size 3.
题解
将每个点变为（x+y,x-y）
这样两点的曼哈顿距离就是(|x1 – x2|，|y1 – y2|)
然后将所有点按x坐标排序
用一个队列，维护队列中元素x坐标的差小于c，不满足则左指针右移
对这个队列中元素的y坐标维护平衡树，如果新加入元素的前驱后继与它的y坐标差值不超过c，则用并查集将他们连在一起
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #define inf 10000000000LL #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,c,ans,mx; int fa[100005],tot[100005]; struct data{ll x,y;int id;}a[100005]; multiset <data> b; set <data>::iterator it; inline bool operator<(data a,data b) { return a.y<b.y; } inline bool cmpx(data a,data b) { return a.x<b.x; } int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } inline void un(int x,int y) { int p=find(x),q=find(y); if(p!=q) { fa[p]=q; ans--; } } void solve() { b.insert((data){0,inf,0});b.insert((data){0,-inf,0}); int now=1;b.insert(a[1]); for(int i=2;i<=n;i++) { while(a[i].x-a[now].x>c) { b.erase(b.find(a[now])); now++; } it=b.lower_bound(a[i]); data r=*it,l=*--it; if(a[i].y-l.y<=c) un(a[i].id,l.id); if(r.y-a[i].y<=c) un(a[i].id,r.id); b.insert(a[i]); } } int main() { n=read();c=read();ans=n; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=n;i++) { int t1=read(),t2=read(); a[i].x=t1+t2,a[i].y=t1-t2;a[i].id=i; } sort(a+1,a+n+1,cmpx); solve(); for(int i=1;i<=n;i++) tot[find(i)]++; for(int i=1;i<=n;i++) mx=max(mx,tot[i]); printf("%d %d\n",ans,mx); return 0; } |
Subscribe
计数器 9854522
OI 课件=>
OI 课件=>