Incinerate | Serendipity

type

status

date

slug

summary

题目描述

为了毁灭人类，怪物协会向地球表面派出了只怪物。第只怪物拥有的健康和的力量。

杰诺斯的最后一击是 "真螺旋焚化炮"，它可以对所有活着的怪物造成的伤害。换句话说，杰诺斯一次攻击就能使所有怪物的生命值降低 (如果 )。

然而，杰诺斯每次攻击后，怪物们都会前进。在它们的共同努力下，杰诺斯的攻击伤害会减少最弱怪物的生命值。也就是说，每次攻击后，的数值都会减去当前所有存活怪物中最小的。

吉诺斯能成功杀死所有怪物吗？

输入的第一行包含一个整数 ( ) 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含两个整数和 ( )。( )--怪物数量和基诺斯的初始攻击伤害。随后两行分别包含个整数，描述了数组和 ( )。

保证所有测试用例的之和不超过。

对于每个测试用例，如果 Genos 能杀死所有怪物，则打印答案 "YES"(不带引号)，否则打印 "NO"。

注

在第一个示例中，吉诺斯第一次攻击后， h 和 k 将更新为：

第二次攻击后

第三次攻击后

第四次攻击后

由于基诺斯可以杀死所有怪物，所以答案是 "YEA"。

这道题主要用到了排序算法，我们有两种排序方法，第一种是对怪兽的生命值进行排序，另一种是对怪兽的力量进行排序。

首先我们来看第一种排序方法，对怪物按健康状况从高到低排序。

现在，我们要对每次攻击后存活的怪物进行计数。这可以通过为每次攻击在数组上应用 upperbound( ) 来实现。受到的总伤害可以存储在一个单独的变量中并进行更新。

若要找出存活的最弱怪物的威力，我们只需预先计算后缀数组中怪物的最小威力。换句话说，也就是。

时间复杂度：

我们呢再来看第二种排序方法，对怪物的力量从低到高排序，只有生命值大于总伤害值的怪物才算活着，而每次遇到这样的怪物时，它都是当前最弱的一个，因此我们需要攻击，直到总伤害值超过当前怪物的生命值。

如果在伤害降为0之前能杀死，也就是遍历到最后一个怪物，答案就是“YES”，否则就是“NO”。

时间复杂度：。

下面给出第二种方法的完整代码：