本题是一道经典的贪心问题,考虑两个火箭 i
和 j
,在两个火箭均可发射时,若 i
的损失费 p[i]
大于 p[j]
,且 i
在 j
之后发射,两个火箭的损失费之和
cost1=p[i]⋅(t[i]−i)+p[j]⋅(t[j]−j)
若交换两个火箭发射顺序,则两个火箭的损失费之和
cost2=p[i]⋅(t[j]−i)+p[j]⋅(t[i]−j)
作差得
cost1−cost2=p[i]⋅(t[i]−t[j])+p[j]⋅(t[j]−t[i])&=(p[i]−p[j])⋅(t[i]−t[j])
又 p[i]>p[j],t[i]>t[j],所以 cost1>cost2,即对于已经可以发射的两个火箭,损失费较大的火箭先发射所产生的损失费最小。
由以上证明可以看出,本题中在当前可以发射的火箭中,损失费较大的火箭应该排在前面,同时还要考虑到火箭从当前不可发射到当前可以发射的状态转换,所以可以使用一个优先队列来维护当前可以发射的火箭集合,每次弹出损失费最大的火箭,将损失费加入答案,并放入新增的可以发射的火箭。
同时,由数据范围不难发现运算过程中使用 int
会导致溢出。
代码如下:
1 |
|