正经题解|超能战士
2024-03-22 13:32:14
发布于:浙江
25阅读
0回复
1点赞
题目大意
有 只怪兽,每只怪兽都有生命值 和攻击力 ,超能战士每次可以对所有活着的怪兽造成 点伤害。
怪兽会在每次超能战士攻击后进行反击,活着最弱的怪兽会降低超能战士攻击伤害,降为
题意分析
求问超能战士能不能消灭所有的怪兽
解题思路
从题中可以发现,超能战士的攻击力 同时可以看做是超能战士的血量,当 的时候,如果场上还有怪兽,则不能消灭所有怪兽。
超能战士每进行一次攻击可以消灭所有当前血量 的怪兽,我们可以模拟这个过程直到超能战士的攻击力 ,所以重点考虑怎么去模拟这个过程,如果用暴力的方式,一遍一遍让怪兽的血量减去 ,那么复杂度为 ,超时!
实际上我们只需要找到第一个不能被杀死的怪兽,即第一个血量 的怪兽。
我们可以先按照血量从小到大排序,我们记找到第一个血量 怪兽的下标为 ,那么 的怪兽都视为死亡,的怪兽都为存活。由于血量是有序的了,满足单调性,我们可以使用二分。由于怪兽的血量是会变化的,在二分的时候要将怪兽的血量减去超能战士累积攻击的伤害。
我们还有个问题没有解决,如何在存活的怪兽中,找到最弱的,即攻击力最小的。存活的下标区间为 ,我们可以贪心最小值,倒着遍历不断看右边的最小值与当前值哪一个更小,来维护一个最小值数组。
时间复杂度解析
维护小最值数组,需要遍历所有怪物,复杂度为
查找第一个不能杀死的怪物,用到了二分,直到 时,结束模拟过程。复杂度为
代码演示
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int t,n,k;
int s = 0;
struct w{
int h,p;
}arr[N];
int zx[N];
bool cmp(const w &a,const w &b) {
return a.h < b.h;
}
int fd(int l,int r,int target) {
while(l <= r) {
int mid = (l + r) >> 1;
if (arr[mid].h - s > target)r = mid - 1;
else l = mid + 1;
}
return l >= n ? -1 : l;
}
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
s = 0;
cin >> n >> k;
memset(zx,0,sizeof zx);
for(int i=0;i<n;i++) cin >> arr[i].h;
for(int i=0;i<n;i++) cin >> arr[i].p;
sort(arr,arr+n,cmp);
int l = 0,r = n - 1;
zx[r] = arr[r].p;
for(int i=r-1;i>=0;i--) {
zx[i] = min(zx[i+1],arr[i].p);
}
while(k > 0) {
int idx = fd(l,r,k);
if (idx != -1) {
l = idx;
}
int p = zx[idx];
s += k;
if (s >= arr[r].h)break;
k -= p;
}
if (s >= arr[r].h) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
这里空空如也
有帮助,赞一个