Link

CF1901 D Yet Another Monster Fight

Question

现在给你一堆怪物，你拥有法术（一个法术可以连续攻击这n个所有怪物），你可以选择任意一个怪物作为法术的第一个攻击目标（伤害为 $x$ ），然后除了第一个攻击目标可以任意，其他攻击目标只能为曾经攻击目标的相邻怪物。然后伤害依次递减，$x ,x-1,x-2,\cdots$ 如果伤害大于等于怪物的血量，则怪物被击杀

现在你第一次攻击目标一定是最优的，问你最坏情况下，$x$ 需要多少才能一次法术把所有怪物击杀完毕

Solution

对于一个怪物 $a[i]$ 考虑在 $j$ 处释放，贪心的去向，最坏情况肯定是 $j$ 先往后面衰减，然后往前面衰减，那么到 $i$ 的衰减量就是 $(N-j)-(j-i)=N-i$ ，则在 $j$ 处释放至少需要 $a[i]+(N-i)$

如果在 $i$ 前面释放，则需要的 $x$ 至少 $a[i]+i-1$

那么对于需要在 $j$ 处开始攻击，则 $$x=\max{\max_{i=1}^{{j-1}{a[i]+i-1},\max_{i=j+1}}N {a[i]+N-i},a[i]}$$
对于 $\max_{i=1}^{j-1}{a[i]+i-1}$ 和 $\max_{i=j+1}^N {a[i]+N-i}$ 可以提前预处理出来

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=3e5+5,INF=2e9;
int a[maxn],R[maxn],L[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    // freopen("D.in","r",stdin);
    int N=read();
    for(int i=1;i<=N;i++) a[i]=read();
    for(int i=1;i<=N;i++){
        int now=N-i+a[i];
        L[i]=max(L[i-1],now);
    }
    for(int i=N;i;i--){
        int now=i-1+a[i];
        R[i]=max(R[i+1],now);
    }
    int ans=INF;
    for(int i=1;i<=N;i++){
        int now=max(a[i],max(L[i-1],R[i+1]));
        ans=min(ans,now);
    }
    printf("%d\n",ans);
    return 0;
}