英雄卡初始存在 \(A\) 点力量值和 \(B\) 点生命值。有 \(n\) 张怪物卡,第 \(i\) 张怪物卡拥有 \(a_i\) 点力量和 \(b_i\) 点生命值。任意卡的生命值 \(\leq 0\) 则阵亡。
在任意一步中可以选择一张怪物卡与英雄卡决斗,战斗结束后双方各受到对方力量点数的伤害。询问英雄卡是否可以完全消灭所有怪物卡。
观察一:消灭每张怪物卡需要进行的决斗次数是固定的,英雄卡受到的伤害总和是固定的。
观察二:需要获胜的决斗次数固定,所以英雄卡只需要在倒数第二轮决斗存活,即可取得胜利。
于是若 \(B - \sum_{i = 1}^{n} \lceil \frac{b_i}{A} \rceil \cdot a_i + a_k > 0\) ,则英雄可以将所有的怪物卡消灭。\(k\) 是最后一只怪物的位置。显然找到 \(a_i\) 最大的位置令为 \(k\) 即可。
view
#include <bits/stdc++.h>
void solve(){
int A, B; std::cin >> A >> B;
int n; std::cin >> n;
std::vector<int> a(n+1), b(n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
for (int i = 1; i <= n; i++) std::cin >> b[i];
long long sum = 0;
for (int i = 1; i <= n; i++) sum += (1LL * b[i] + A - 1) / A * a[i];
std::cout << (B - sum + *std::max_element(a.begin() + 1, a.end()) > 0 ? "YES" : "NO") << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}