刷野|
liuhongyang123 · · 题解
题目大意
初始有
-
普通攻击：消耗
0 点能量值，选择一只怪物并使其血量减少一点。 -
天音波：消耗
1 点能量值，选择一只怪物并使其血量减少两点。 -
天雷破：消耗
1 点能量值，使所有怪物血量减少一点。
一开始是 Zayin 先攻击，每次攻击后剩余的每只怪物会对 Zayin 造成一点伤害。
求在最优的策略下，击败
解法
其实不难发现这是一道贪心题，首先说一下贪心策略：
-
只要还有能量（前提）剩的怪物数量大于二或者剩下的怪物数量小于等于二且剩下的怪物中至少有一个血量为一那么就使用天雷破。
-
如果不满足条件一且还有能量那么就使用天音波。
-
如果没能量了就只能使用普通攻击。
PS：如果用个体伤害那么要从剩下血量最少的怪开始打。
简单证明
其实我们用反证法可以很容易得出刚刚所说的结论。
-
单体打要打血量最少的怪
这不显而易见，因为少的打的快，后期打你的怪会少很多。 -
怪物数大于二用范围攻击。反证 ：如果用天音波，单体的一个怪是可以打的比天雷破快，但是到后期一大堆怪毫发无损，你又要一个一个地打，要弥补之前任性的代价，而天雷破这时对怪物们的伤害会比天音波大得多的，但要注意如果怪物是小于三那么天雷破和天音波对怪物们的伤害是一样的，但天音波刷怪的速度会比天雷破快所以用天音波。
-
有一滴血的怪时用天雷破，如果用天音波那岂不是用大炮打蚊子。
-
如果没能量了那没得选只能用普通攻击。
最后
请允许我附上代码。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long MAXN=1E6+10;
long long n,m,cnt,a[MAXN],b[MAXN],nl,sum;
void solve(long long l,long long r,long long pa[],long long pb[]){
if(r==l) return;
long long mid=(l+r)>>1;
solve(l,mid,pa,pb);
solve(mid+1,r,pa,pb);
long long id1=l,id2=mid+1;
for(long long i=l;i<=r;i++){
if(id2>r||(id1<=mid&&pa[id1]<pa[id2])) pb[i]=pa[id1],id1++;
else pb[i]=pa[id2],id2++;
}
for(long long i=l;i<=r;i++) pa[i]=pb[i];
}
long long ans;
signed main(){
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
solve(1,n,a,b);
while(m>0&&n-cnt>2){
sum++;
m--;
while(a[cnt+1]-sum<=0&&cnt+1<=n) cnt++;
ans+=n-cnt;
}
while(m>0&&cnt<n){
if(a[cnt+1]-sum==1){
m--;
cnt++;
if(a[cnt+1]-sum==1) cnt++,ans--;
else if(cnt+1>n) ans--;
sum++;
ans++;
continue;
}
a[cnt+1]-=2;
m--;
if(a[cnt+1]-sum>0) ans+=n-cnt;
else cnt++,ans+=n-cnt;
}
while(cnt<n){
ans+=(n-cnt)*(a[cnt+1]-sum-1)+(n-cnt-1);
cnt++;
}
printf("%lld",ans);
return 0;
}