P10072 题解
Guizy
·
·
题解
修改了第 8 行，可以通过 Hack。
题目大意
给你 n,m 和一个数列 a_1,a_2,\ldots,a_{n-1},a_n，分别代表怪物数量，使用技能的次数，每只怪物的血量。
-
技能 1：对每只怪物造成 1 点血量伤害。
-
技能 2：对其中一只怪物造成 2 点血量伤害。
-
普攻：对其中一只怪物造成 1 点血量伤害。
每一次攻击后，会受到当前存活怪物数量的伤害。
求把它们全部打死的最小伤害。
思路
考虑贪心：
应该很好理解，回合数不变，怪兽死的平均时间更早，受到伤害更小。
- 怪兽数等于 $2$ 时，优先使用 $2$ 技能。
回合数不变，有一只先死。
- 怪兽数等于 $1$ 时，优先使用 $2$ 技能。
显然。
- 特殊情况：怪兽数等于 $2$ 且有一只血量为 $1$ 时，优先使用 $1$ 技能。
打死一只的同时，还可以对另一只造成 $1$ 点伤害。
## 实现
受到[这位大佬](https://www.luogu.com.cn/blog/hxjismysontoo/solution-p10072)的题解的启发，我们可以循环能量值而不是当前打到的怪物数，有效减少很多码量！
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100001],temp,ans,wz=1;
void work(){
while(a[wz]-temp==0&&wz<=n) wz++;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);
int num=n+1;
for(int i=1;i<=m&&wz<=n;i++){//wz代表打的是第几只怪
if((n-wz+1)>2) temp++,work();//2只以上先用AOE
else if(a[wz]-temp==1) temp++,work();//否则判一下是否是1
else{//否则暴击
a[wz]-=2;
if(a[wz]-temp==0) wz++;
}
ans+=n-wz+1;
}
for(int i=wz;i<=n;i++) ans+=(n-i+1)*(a[i]-temp)-1;
//因为打最后一下的时候怪就会死，不会造成伤害所以-1
printf("%lld",ans);
}
```