Codeforces 1480B. The Great Hero（阅读模拟题，注意数据范围和攻击顺序）

题意

你有一个英雄，攻击力为A，生命值为B。（没有经验、金币等机制，攻击力与生命值不可提高）

游戏中有n只怪，怪的攻击力为a[i]，生命值为b[i]。

每次你可以选择一个怪攻击，攻击后你的生命值变为B-a[i]，怪的生命值变为b[i]-A。

不论你是否死亡，如果你能消灭所有的怪，获得胜利。否则失败。

解题思路

遍历攻击所有的怪，模拟场景扣除英雄的血量。

若英雄的血量足以支撑让所有怪的血量都扣除到小于等于0，则获得胜利。否则失败。

注意

数据范围超过了有符号整型的最大值2^31，所以需要用long long。（因为没有用long long导致这道题WA了）

最后攻击攻击力最高的怪。因为极端情况最后一只怪只差一刀的情况下，主角只需要1血就可获得胜利，超过1的血量都是溢出的。这种情况下，最后攻击攻击力最高的怪，可以尽量减少血量溢出，最大可能完成任务。（我最开始想的是按照攻击力从小到大遍历，一样可以AC这道题，但是却让时间复杂度从O(n)变成了O(nlogn)）

C++ Code （优化后）

#include <bits/stdc++.h> using namespace std; typedef long long ll;int t; ll A, B, n; ll a[100010]; ll b;int main() {ios::sync_with_stdio(false);cin >> t;while (t--) {cin >> A >> B >> n;ll mxA = 0; // 攻击力最高的怪的攻击力。 for (int i = 0; i < n; ++i) cin >> a[i], mxA = max(mxA, a[i]);for (int i = 0; i < n; ++i) {cin >> b;B -= (b+A-1)/A*a[i];}// 回退一刀，看最后一刀前英雄的血量是否大于0 B+mxA > 0?puts("YES"):puts("NO");}return 0; }

C++ Code （优化前）

#include <bits/stdc++.h> using namespace std; typedef long long ll;int t; ll A, B, n;struct node {ll a;ll b; } arr[100010];bool cmp(node x, node y) {return x.a < y.a; }int main() {ios::sync_with_stdio(false);cin >> t;while (t--) {cin >> A >> B >> n;for (int i = 0; i < n; ++i) {cin >> arr[i].a;}for (int i = 0; i < n; ++i) {cin >> arr[i].b;}// 将怪按攻击力排序 sort(arr, arr + n, cmp);// 不攻击最后一只怪 int cost = 0;// 默认可以胜利，通过血量改变标志位 bool flag = true;for (int i = 0; i < n - 1; ++i) {ll num = arr[i].b / A;arr[i].b -= num * A;if (arr[i].b > 0) {num++;arr[i].b -= A;}B -= num * arr[i].a;// 如果血量归零，则失败 if (B <= 0){flag = false;break; }}// 特判最后一只怪 int i = n - 1;ll num = arr[i].b / A;arr[i].b -= num * A;if (arr[i].b > 0) {num++;arr[i].b -= A;}B -= num * arr[i].a;// 回退一刀，若最后一刀前血量归零，则失败 if (B <= -arr[i].a)flag = false;if (flag)puts("YES");elseputs("NO");}return 0; }

总结

以上是生活随笔为你收集整理的Codeforces 1480B. The Great Hero（阅读模拟题，注意数据范围和攻击顺序）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。