[集训Day1]打怪兽(贪心)

题目描述

有n只怪兽,初始你有k点血量,打第i个怪兽至少需要aia_i的血量,打完第i个怪兽之后会掉bib_i的血量,你可以按照任何顺序依次打完所有怪兽,并给出一种方案。

n106ai,bi109\large n\leq10^6\qquad a_i,b_i\leq10^9

题目解析

n = 2n\ =\ 2

第一组:a1b1a_1\qquad b_1
第二组:a2b2a_2\qquad b_2

则k需要满足条件
kmax(a1,a2)\large k\geq\max(a_1,a_2)
②若先打第一组
kb1a2\large k-b_1\le a_2
    ka2+b1\large \implies k\ge a_2+b_1
同理,若先打第二组
ka1+b2\large k\ge a_1+b_2

比较a2+b1a_2+b_1a1+b2a_1+b_2的大小
由于kk在操作之后会变小,所以让大的先打,这样才能尽量多地打。

    a2+b1?>a1+b2\implies a_2+b_1?>a_1+b_2
    a2b2?>a1b1\implies a_2-b_2?>a_1-b_1
    \implies扩展到n个数,我们只需要将anbna_n-b_n从大到小排列,依次执行就好了。

程序代码

文章作者: Tim
文章链接: http://itstim.xyz/%E9%9B%86%E8%AE%ADDay1-%E6%89%93%E6%80%AA%E5%85%BD-%E8%B4%AA%E5%BF%83/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tim's Blog
支付宝恰饭打赏
微信恰饭打赏