bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 (曼哈顿距离的转化【拆点】+set+并查集)

http://www.lydsy.com/JudgeOnline/problem.php?id=1604
题意:了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的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均同属一个群.
给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

思路:一开始并没有什么思路…入手点是关于曼哈顿距离的转化。

先看曼哈顿距离的定义

|x1x2|+|y1y2|

拆绝对值

x1x2+y1y2x1x2+y2y1

x2x1+y1y2x2x1+y2y1

|x1+y1(x2+y2)||x1y1(x2y2)|

x1+y1xx1y1y

|x1x2||y1y2|

所以原要求1转化为

max(|x1x2|,|y1y2|)<=c

引用自:http://blog.csdn.net/wzq_QwQ/article/details/47746091

 

这样就有思路了。如果两个点属于同一个群,那么必须这两个点的x的差在c范围内,并且两个点的y的差也在范围内。 我们可以先按照一个 坐标排序,不妨以x为关键字排序,然后维护一段点的序列,使得这段序列中的所有的点的横坐标(其实就是最大减去最小)的差都在c范围内。然后对于序列中的所有点,我们想要知道有没有群“接纳”最新加入的点,二分找到比当前新加入点的纵坐标大的最小值和比当前新加入点的纵坐标小的最大值(set的lower_bound 第一次用),判断是否满足纵坐标的差在c的范围内。如果是,则用并差集合合并一下。

用multiset的原因是经过变换后点的坐标可能重复,以及multiset删除元素的时候不能直接删,因为会把所有相同的值删掉。

 

重要的话再说一遍:这道题最关键也是最大的收货就是,关于曼哈顿距离的变换。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz