这题需要考虑的细节有点多。
假设数组nums,首先需要证明的是,对于排序后的数组,元素nums[i](不考虑最后一个元素)如何在更小的群体伤害次数下被击破。如果nums[i]能够被k次奥术冲击击破,那么nums[i-1]一定也可以,相应的之前的一定都可以。由于裂变新星伤害一定大于0,那么如果触发更多次裂变新星,也能减少奥术冲击的使用。
所以贪心的思路如下:
(1)首先将数组进行排序,从前往后遍历数组,将尽可能靠前的较小元素护盾值削减到50%及以下(这种削减对后面的更大元素也同时造成),用两个变量cntE和cntR分别统计奥术冲击和裂变新星的使用次数。
在魔法试炼中,有 n 个元素灵,第 i 个元素灵的初始护盾值为 ai。你需要使用法术击破它们的护盾。
你可以主动释放「奥术冲击」:每释放一次,对所有存活的元素灵造成 P 点护盾削减。
当任意一个元素灵的当前护盾值首次下降到其初始护盾值的 50% 及以下时,如果场上仍有至少一个存活的元素灵,则会自动触发一次「裂变新星」,对所有存活元素灵再造成 S 点护盾削减。如果一次攻击(包括奥术冲击和裂变新星)导致多个元素灵同时满足上述条件,则会连续触发多次裂变新星,直至没有新的满足条件的存活元素灵或所有元素灵的护盾降至 0 以下为止。在连续触发的裂变新星全部结束之前,你无法再次释放奥术冲击。
你的任务是计算:按照以上规则完成试炼(即所有元素灵的护盾值 ≤0),一共需要释放多少次奥术冲击,以及一共触发了多少次裂变新星。
约束:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册