icontofig | 发布于 2019-08-07 22:04:05 | 阅读量 270 | 左偏树
发布于 2019-08-07 22:04:05 | 左偏树
 Description在一个忍者的帮派里,一些忍者们被选中派遣给顾客,然后依据自己的工作获取报偿。在这个帮派里,有一名忍者被称之为 Master。除了 Master以外,每名忍者都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水,同时使得支付的薪水总额不超过你的预算。另外,为了发送指令,你需要选择一名忍者作为管理者,要求这个管理者可以向所有被派遣的忍者 发送指令,在发送指令时,任何忍者(不管是否被派
继续阅读
icontofig | 发布于 2019-08-03 20:58:54 | 阅读量 253 | 左偏树 并查集
发布于 2019-08-03 20:58:54 | 左偏树 并查集
HDU 1512 Monkey King 左偏树 并查集
题目大意有n只猴子,每只猴子有自己的能力值,它们会有m次冲突,每次冲突若两只猴子不在同一阵营,则选出两只猴子所在阵营中能力值最高的猴子较量,能力值高的猴子会获胜,并且能力值减半,失败的一方加入胜利方的阵营,问每一次冲突获胜阵营出战的猴子在获胜后的能力值。若同一阵营则输出-1。 题解每个阵营选出最大值,显然是要维护一个堆什么的,但是至于合并怎么办? 可并堆其实有很多种,这里感觉还是左偏树比较简单。 我们维护左偏树,每一个阵营对应一棵左偏树。 在发生一次冲突时,我们用并查集查询两只猴子所在阵营中能力值最大的猴子(在左偏树的维护过程中保证并查集的根即是左偏树的根),若在一个阵营,直接输出-1;若不在
继续阅读