主题

主题

 
   

1854: [Scoi2010]游戏

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=1854

Description

lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。

当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 

游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。

 现在lxhgww想知道他最多能连续攻击boss多少次?

Input

输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值

Output

输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。

Sample Input

3

1 2

3 2

4 5

Sample Output

2

HINT

【数据范围】

对于30%的数据,保证N < =1000

对于100%的数据,保证N < =1000000


个人解法:

终于尝试完全自己独立思考。

自然想到把一个装备视为一条边,把权值视为点。之后我们发现:

  • 如果一个大小为size的连通块是一棵树,那么可以构成里面任意size-1的点权,如果存在一个环,包括重边自环,都可以构成连通块里面所有的点权。

很像POI2008的CLO一题来着。

最开始想到二分答案x,然后打算把所有点权最大值不超过x的连在一起,不过似乎这样并不能保证啥,好像还把单调性破坏了来着?

后来又想了一下,如果二分不太好的话,不如直接枚举,边枚举边合并,也是可以支持的。因为可以枚举到x的必要条件是1到x-1都是枚举过并且判断为可行的。不过还是没有找到一个较好的停止点。

后来思考会不会是先把全部的边都加入进来。那么发现如果仅仅用这个点所在的连通块上一棵树这个条件似乎不太够。

考虑到如果这个点还比较小,尽管是在一棵树里面,还是可以实现的。随着这棵树所使用到的节点越来越大,到最后这棵树不能再满足全部节点都被选择的时候,就是用到了这棵树的权值最大的节点的时候。

于是我们枚举x,用“x所在连通块没有环”+“x是所在连通块权值最大的点”两个条件来判断即可。

至于做法,我们可以类似于POI2008的CLO一题,维护tag(连通块是否有环),maxn(连通块最大值)即可。


代码如下:

https://code.csdn.net/snippets/2201922


此题大概也让我搞懂了并查集对集合信息的维护,只需要在合并的时候更新,以及在初始化Fa的时候更新即可。

 
 
评论