[HDU1512/ZOJ2334/SCU3080/Luogu1456]Monkey King(左偏树,并查集)

发布于 2018-02-07  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU1512/ZOJ2334/SCU3080/Luogu1456]Monkey King(左偏树,并查集)

Description

Once in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can't avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.
Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2).
And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.

Http

HDU
ZOJ
SCU
Luogu

Tag

左偏树,并查集

题目大意

有若干只猴子,开始互相都不认识,两只不认识的猴子会从让它们认识的猴子中最厉害的猴子来打一架,然后就互相认识了。打架的猴子厉害值除以二,求每一次打完架后这些刚刚认识的猴子中最厉害的。

解决思路

左偏树实现可并堆,每次取堆顶分离出来,除以二再加进去,合并堆。并查集维护一只猴子所在的堆的根方便查找。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU1512/ZOJ2334/SCU3080/Luogu1456]Monkey King(左偏树,并查集)


HNCJ OIer 一枚