遇到一个优先队列问题，求解答。
Codancer 终于抵达了恶龙的城堡。现在他在城堡周围摆放了 n 枚电力炸弹，每个电力炸弹有两种属性 m 和 p，只有已经引爆了 m 枚电力炸弹或者 Codancer 直接花费 p 的电力，第 i 枚炸弹才会被引爆，现在 Codancer 想使用最少的电力引爆所有的炸弹，请计算最少需要多少电力？第一行是一个正整数 n，代表有 n 枚电力炸弹。接下来输入n 行，每行两个正整数m和p，代表炸弹的属性。(1<=n<200000,1<=p<=100,1<=m<=n)输出最少花费多少的电力。
展开
收起
1
条回答
写回答
写回答
-
花费8电力引爆第3枚炸弹，那么第1枚就会被自动引爆，那么第2枚也会被 自动引爆。这种方案的花费是最小的。
炸弹的引爆顺序如图所示： 本题使用贪心策略，考虑按照所需要的电力从大到小排序，假设从第i+1枚到第 n 枚炸弹已经用电力引爆的炸弹个数为cnt，由于在 [1,i-1] 最多再引爆 i-1枚炸弹， 如果此时 i-1+cnt<mi，说明就需要再花费电力引爆，但是必须要选择需要的电力最 少的，因此可以用优先队列维护，直接取出栈顶即可。 则输入：3 [[1,5],[2,10],[2,8]]
输出：82021-12-23 18:38:49赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
