题解 CF1480B 【The Great Hero】

珂能并不会有更好的阅读体验

Description

题目 Link

• 珂朵莉需要把 $\color{skyblue}\text{『深浅值藏的第六兽}\cdot\text{Timere}\cdot\text{恐惧』}$ 全部杀光。
• 珂朵莉的攻击力为 $A$，生命值为 $B$。
• 一共有 $n$ 只「第六兽」，第 $i$ 只兽的攻击力为 $a_i$，生命值为 $b_i$。
• 在珂朵莉和第 $i$ 只「第六兽」的战斗中，珂朵莉每次可以对这只兽造成 $A$ 点伤害，但同时，兽也会对珂朵莉造成 $a_i$ 点伤害。
• 如果兽的生命值 $\le 0$，那么这只兽就死了。
• 同理，如果珂朵莉的生命值 $\le 0$，那么珂朵莉的灵魂就会化作『星尘』消失，只剩下一具没有灵魂的躯壳。
• 但特殊的是，如果此时只剩一只「第六兽」；
• 并且此时这只「第六兽」剩余的生命值低于珂朵莉的攻击力 $A$，但珂朵莉剩余的生命值也低于这只「第六兽」的攻击力；
• 那么珂朵莉在化作『星尘』消散前，还可以发动一次攻击，杀死这只兽，也就是杀死了所有兽。
• 现在给定每只兽与珂朵莉的生命值与攻击力，请你帮珂朵莉算出来，她是否能杀光所有的「第六兽」。
• $t$ 组数据，$1\le t\le 10^5,1\le A,B,a_i,b_i\le 10^6,\sum n\le 10^5$。
  （设定是我瞎编的，与原作可能不太符合，不管啦qwq）

Solution

对于第 $i$ 只兽，珂朵莉需要 $\left\lceil\dfrac{b_i}{A}\right\rceil$ 次攻击才能杀死。

也就是说，珂朵莉想要杀死第 $i$ 只兽，需要消耗 $\left\lceil\dfrac{b_i}{A}\right\rceil\cdot a_i$ 点生命值。

那消灭所有兽之后，珂朵莉的生命值会减少 $\sum\limits_{i=1}^n\left\lceil\dfrac{b_i}{A}\right\rceil\cdot a_i$，也就是还剩 $B-\sum\limits_{i=1}^n\left\lceil\dfrac{b_i}{A}\right\rceil\cdot a_i$ 点生命值。

如果这个值大于 $0$，那就代表着：珂朵莉可以杀光所有兽，并且最后存活。

那就不用管了，直接就是 YES。

但是如果这个值小于等于 $0$，那么有可能珂朵莉还能通过最后一击杀光所有兽，与最后一只兽同归于尽。

唔，这样的话......

那么我们考虑这个值：$d_k=B-\sum\limits_{i=1}^n\left\lceil\dfrac{b_i}{A}\right\rceil\cdot a_i+a_k$。

如果这个值大于 $0$，那么就说明珂朵莉能够杀光所有兽，且最后杀的一只是第 $k$ 只兽。

小于等于 $0$，则说明珂朵莉无论如何都杀不掉最后一只兽。

那么我们先 $O(n)$ 计算 $\sum\limits_{i=1}^n\left\lceil\dfrac{b_i}{A}\right\rceil\cdot a_i$，然后 $O(n)$ 计算出 $d_1,d_2,\cdots,d_n$。

只要 $d_1,d_2,\cdots,d_n$ 中有一个大于 $0$，那就说明珂朵莉可以杀光所有兽，输出 YES。

都小于 $0$ 则输出 NO。

时间复杂度 $O(n)$。

然而 $\sum\limits_{i=1}^n\left\lceil\dfrac{b_i}{A}\right\rceil\cdot a_i$ 最大可以到 $10^6\times10^6\times10^5=10^{17}$，所以：

记！得！开！long long！

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<iostream>

#define MAXN 100005
#define int long long

using namespace std;

int A,B,n;
int t;

int a[MAXN],b[MAXN];

int myceil(int x,int y){
    if(x%y==0)return x/y;
    else return (int)(x/y)+1;
}

void solve(){
    
    cin>>A>>B>>n;

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }

    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=myceil(b[i],A)*a[i];
    }

    bool f=0;
    for(int i=1;i<=n;i++){
        if(B-sum+a[i]>0){
            cout<<"YES\n";
            f=1;
            break;
        }
    }
    if(!f)cout<<"NO\n";
}

signed main(void){

    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}