简单题做了好久,哈哈。
题目分析
首先,对于单个怪物,先将它的血量通过取余处理到小于 \(a+b\) 的时候,因为无论怪物血量多少,如果大于 \(a+b\) ,显然不可能出现最后一击。
设余数为 \(m\) ,在不用特殊能力的情况下就只能击杀 \(m \le a\) 且 \(m\) 不为 \(0\) 的怪物。
然后枚举对于每一个怪物,如果想要击杀它需要耗费多少次特殊能力。由于每一个怪物的贡献都为 \(1\) ,因此直接从小往大取即可。
时间复杂度:\(O(n \log n)\) 。
贴上代码
#include<bits/stdc++.h>
// #define int long long
#define debug puts("Shiina_Mashiro_kawaii")
#define ok puts("T")
#define no puts("F")
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*f;
}
const int maxn=2e5+5;
int n,a,b,k;
int ans;
int h[maxn];
inline void init(){
n=read();a=read();b=read();k=read();
for(register int i=1;i<=n;++i) h[i]=read()-1;
for(register int i=1;i<=n;++i){
h[i]%=a+b;h[i]/=a;
}
sort(h+1,h+n+1);
}
int main(){
init();
for(register int i=1;i<=n;++i){
if(h[i]<=k){
ans++;k-=h[i];
}
}
printf("%d",ans);
}
标签:CF1296D,puts,int,题解,怪物,define
From: https://www.cnblogs.com/yizhixiaoyun/p/17109226.html