| 题目名称 | 526. [HDU 1512] 爱争吵的猴子 |
|---|---|
| 输入输出 | monkeyk.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2010-12-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：119， 提交：265， 通过率：44.91% | ||||
 AAAAAAAAAA |
100 | 0.098 s | 0.89 MiB | C++ |
 gyming |
100 | 0.146 s | 9.85 MiB | C++ |
 hzoi2017_nzy |
100 | 0.167 s | 4.10 MiB | C++ |
|
hzoi2017_nzy |
100 | 0.172 s | 4.10 MiB | C++ |
|
gyming |
100 | 0.177 s | 9.85 MiB | C++ |
 Samle |
100 | 0.179 s | 1.65 MiB | C++ |
 远航之曲 |
100 | 0.188 s | 2.23 MiB | C++ |
 ztx |
100 | 0.188 s | 5.66 MiB | C++ |
|
gyming |
100 | 0.195 s | 9.85 MiB | C++ |
 真呆菌 |
100 | 0.198 s | 2.20 MiB | C++ |
| 关于 爱争吵的猴子 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
只会自己的乱YY的启发式并查集，QAQ，Orz 会左偏树的大佬
| ||||
|
数据好水。。。
 LGLJ
2019-06-18 14:47
12楼
| ||||
|
第一道左偏树
AAAAAAAAAA
2017-07-01 22:04
11楼
| ||||
|
左偏树左偏树..........
| ||||
|
QAQ 必须加启发式合并，不然会T4个点
 Janis
2016-11-03 22:28
9楼
| ||||
|
| ||||
|
回复 @天一阁 :
咳 、、正解是左偏树吧、、、虽然我用并查集写的、、、、因为左偏树pascal写不过、、  ConanQZ
2016-04-04 15:56
7楼
| ||||
|
左偏树 Get√
果然还是太嫩了QAQ  葳棠殇
2016-03-25 20:49
6楼
| ||||
|
按高度的启发式合并真是太暴力了！！！！4.9s->0.4s啊！！！
| ||||
|
回复 @天一阁 :
从哪弄得 = = ztx
2014-07-03 20:04
4楼
| ||||
Hale
sxysxy
FoolMike
一個人的雨【问题描述】
在一个森林里，住着 $N$ 只好斗的猴子。开始，他们各自为政，互不相干。但是猴子们不能消除争吵，但这仅仅发生在两只互不认识的猴子之间。当争吵发生时，争吵的两只猴子都会求助他们各自最强壮的朋友，并且决斗。当然，决斗之后，两只猴子及他们所有的朋友都相互认识了，并且成为朋友，争吵将不会在他们之间发生。
假定每一只猴子有一个强壮值，在每次决斗之后变为原来的一半（例如，$10$ 将为变为 $5$，$5$ 将会变为 $2$）。假定每一只猴子认识他自己。也就是当他发生争吵，并且自己是他的朋友中最强壮的，他将代表自己进行决斗。
【输入格式】
有几组测试数据,每组测试数据由两部分构成。
第一部分：第一行有一个整数 $N(N≤100,000)$，表示猴子的数量。下面有 $N$ 行.每行有一个数，表示猴子的强壮值($≤32768$)。
第二部分：第一行有一个整数 $M(M≤100,000)$，表示有 $M$ 次争吵发生。下面有 $M$ 行,每行有两个整数 $x$ 和 $y$，表示在第 $x$ 只猴子和第 $y$ 只猴子之间发生争吵。
【输出格式】
对于每一次争吵，如果两只猴子认识，输出 $-1$，否则输出一个数，表示决斗后朋友中最强壮猴子的强壮值。
【输入样例】
5 20 16 10 10 4 5 2 3 3 4 3 5 4 5 1 5
【输出样例】
8 5 5 -1 10
【题目来源】
HDU 1512 Monkey King