【ZOJ2334 猴子大王】

【题目描述】

森林里,住着N只好斗的猴子。起初,它们相互都不认识。这些猴子经常发生争吵,但是争吵只会发生在两只相互不认识的猴子之间。当它们争吵时,两只猴子都将各自邀请他们最强的朋友来决斗。当然,决斗后,决斗的两只猴子和他们所有的朋友彼此认识了,认识后的猴子将不再发生争吵,不管他们之间有没有矛盾。

假设每一只猴子都有一个战斗力值,两只猴子战斗后,各自的战斗力值将减少到原来的一半(比如:10将减少到5;5将减少到2)。

我们还假设每个猴子都认识自己,当他是所有朋友中战斗力最强的一个,他自己就要去决斗。

 

【输入格式】

有多组测试数据。每组数据包含两部分:

第一部分的第一行是一个整数N(N≤100,000),表示猴子数量。接下来有N行,每行一个整数,表示每只猴子的战斗力值(战斗力值≤32768)。

第二部分的第一行是一个整数M(N≤100,000),表示有M次决斗。接下来有M行,每行两个整数X和Y,表示有第X只猴子和第Y只猴子将发生决斗,如果X和Y认识,则放弃决斗。

 

【输出格式】

对于每次决斗,决斗前,如果两只猴子认识彼此,放弃决斗,输出-1,否则输出决斗后所有朋友中战斗力最强猴子的战斗值。

 

【输入样例】monkey.in

5

20

16

10

10

4

5

2 3

3 4

3 5

4 5

1 5

【输出样例】monkey.out

8

5

5

-1

10

可并堆模板题,用左偏树做的。大意就是对每个猴子建一颗左偏树,维护猴子的朋友用并查集即可,然后两只猴子决斗就取出他们集合(左偏树)的第一个点(最大点)对其进行除以2的操作然后放回原来的左偏树中,然后两棵左偏树合并一下,返回的新的第一个点即是决斗后朋友的最大战斗力。

PS:感觉常数写的好丑QAQ 跑完全部数据花了6750ms QAQ果然我还是太弱了。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*