题解：CF1901D Yet Another Monster Fight

Jerrycyx · 2024-11-11 12:08:58 · 题解

因为每次攻击的怪物都与已被攻击过的怪物相邻，所以被攻击的怪物一定组成一个连通区间，且每次攻击都是在将这个区间向左或向右扩大一个位置。

假设我们选择的位置是 p，初始攻击为 x，考虑最坏情况：

如果要攻击 p 左边某怪物 i，最坏情况是魔法最开始每次都往右边打（(n-p) 次攻击），右边打完了以后再从 p 向左边打到 i（(p-i) 次攻击），算上最初的一次，打到 i 最多需要 (n-p)+(p-i)+1=n-i+1 次攻击，此时还剩下的攻击力为 x-(n-i+1)+1=x-n+i。要击杀这个怪物，攻击力必须大于其血量，所以 x-n+i \ge a_i，转化一下得到 x \ge a_i+n-i。
同理，如果要攻击 p 右边某怪物 i，最坏情况是魔法先往左边打 (p-1) 次，再向右边打 i-p 次打到 i，算上最初一次，一共 i 次攻击。此时还剩下的攻击力为 x-i+1，又因为 x-i+1 \ge a_i，所以 x \ge a_i+i-1。

综上所述，所选择的 x 和 p 需要满足以下条件：

\begin{aligned} x \ge a_i+n-i,&\quad i<p \\ x \ge a_i+i-1,&\quad i>p \\ x \ge a_i,&\quad i=p \end{aligned}

而上述条件可以转化一下：

\begin{aligned} x& \ge \max_{i=1}^{p-1}\{a_i+n-i\} \\ x& \ge \max_{i=p+1}^{n}\{a_i+i-1\} \\ x& \ge a_p \end{aligned}

上面的最大值可以预处理，即可以设 lmax_i = \max_{j=1}^{i}\{a_j+n-j\}，rmax_i = \max_{j=i}^{n}\{a_j+j-1\}。

解法也就出来了，枚举每一个可能的 p，此时的 x 就为 \max\{lmax_{p-1}, rmax_{p+1}, a_p\}，对所有的 x 取最小值即为答案。

核心代码：

for(int i=1;i<=n;i++)
    lmax[i]=max(lmax[i-1],a[i]+n-i);
for(int i=n;i>=1;i--)
    rmax[i]=max(rmax[i+1],a[i]+i-1);
int ans=0x7fffffff;
for(int i=1;i<=n;i++)
    ans=min(ans,max({a[i],lmax[i-1],rmax[i+1]}));

AC 记录 + 完整代码