【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“121.Codancer的炸弹引爆”的解法探究。先来看一下题目内容：

题目详情

等级：困难
知识点：贪心、优先队列
查看题目：Codancer的炸弹引爆

Codancer终于抵达了恶龙的城堡。现在他在城堡周围摆放了n枚电力炸弹，每个电力炸弹有两种属性m和p，只有已经引爆了m枚电力炸弹或者Codancer直接花费p的电力，第i枚炸弹才会被引爆，现在Codancer想使用最少的电力引爆所有的炸弹，请计算最少需要多少电力？

第一行是一个正整数n，代表有n枚电力炸弹。接下来输入n行，每行两个正整数m和p，代表炸弹的属性。(1<=n<200000,1<=p<=100,1<=m<=n)

输出最少花费多少的电力。

示例1
输入：
3
[[1,5],[2,10],[2,8]]
输出：
8
注意
花费8电力引爆第3枚炸弹，那么第1枚就会被自动引爆，那么第2枚也会被自动引爆。

解题方法：

花费8电力引爆第3枚炸弹，那么第1枚就会被自动引爆，那么第2枚也会被自动引爆。

这种方案的花费是最小的。

炸弹的引爆顺序如图所示。

本题使用贪心策略，考虑按照所需要的电力从大到小排序，假设从第i+1枚到第n枚炸弹已经用电力引爆的炸弹个数为cnt，由于在[1,i-1]最多再引爆i-1枚炸弹，如果此时i-1+cnt<mi，说明就需要再花费电力引爆，但是必须要选择需要的电力最少的，因此可以用优先队列维护，直接取出栈顶即可。

时间复杂度：O(n*log（n）)

看完之后是不是有了答题思路了呢，快来练练手吧：121.Codancer的炸弹引爆

在线编程周赛、月赛火热进行中，更有限时答题活动，定制卫衣、双肩背包、机械键盘等多重好礼等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！