在考场上较为实用的在线带修莫队 做法。
2025/1/31...大约 10 分钟
在考场上较为实用的在线带修莫队 O((n+m)n2/3) 做法。
有一个游戏,这个游戏中有若干个英雄和若干个道具,每个英雄存在生命值,每一个道具存在耐久度,每个英雄最多持有一件道具。
游戏开始时,你需要给每一个英雄分配一个道具(可能存在英雄没有道具或道具没有英雄),然后销毁未被分配的道具。
接下来有若干轮,每轮令每个英雄的生命值和每个道具的耐久度减去 (a+b)−1,其中 a 表示存活的英雄数量,b 表示存在的道具数量,当英雄生命值小于等于 0 时即死亡,当道具耐久度小于等于 0 时,或持有它的英雄死亡时即销毁。当没有英雄存活时,游戏结束。你需要最大化游戏的轮数。