Incinerate

题目连接：

Problem - B - Codeforces

---

题目描述

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

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

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

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

输入描述

输入的第一行包含一个整数 $t$ ( $1 \le t \le 100$ ) 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ( $1 \le n, k \le 10^5$ )。( $1 \le n, k \le 10^5$ )–怪物数量和基诺斯的初始攻击伤害。随后两行分别包含 $n$ 个整数，描述了数组 $h$ 和 $p$ ( $1 \le h _ i, p _ i \le 10^9$ )。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出描述

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

示例

输入

text

3
6 7
18 5 13 9 10 1
2 7 2 1 2 6
3 4
5 5 5
4 4 4
3 2
2 1 3
1 1 1

输出

text

YES
NO
YES

说明

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

• $h: [11,0,6,2,3,0]$
• $k: 7-1 = 6$

第二次攻击后

• $h: [5,0,0,0,0,0]$
• $k: 6-2 = 4$

第三次攻击后

• $h: [1,0,0,0,0,0]$
• $k: 4-2 = 2$

第四次攻击后

• $h: [0,0,0,0,0,0]$

由于基诺斯可以杀死所有怪物，所以答案是 “YES”。

---

题解

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

解法一

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

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

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

时间复杂度： $O(nlogn)$

解法二

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

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

时间复杂度： $O(nlogn)$ 。

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

#include<bits/stdc++.h>
using namespace std;
struct g1
{
    int h;
    int p;
}g[100005];

bool cmp(g1 a,g1 b)
{
    return a.p<b.p;
}

void solve()
{
    long long n,k;
    bool flag=true;
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>g[i].h;
    }
    for (int i=1;i<=n;i++)
    {
        cin>>g[i].p;
    }
    sort (g+1,g+n+1,cmp);
    int i=1;
    long long ans=k;
    while(i<=n)
    {
        if (g[i].h>k)
        {
            ans-=g[i].p;  //当前伤害
            k=k+ans;      //累计伤害
        }
        else
        {
            i++;
        }
        if (ans<0)
        {
            flag=false;
            break;
        }
    }

    if (flag)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return ;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t)
    {
        t--;
        solve();
    }   
}