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;
}