D. Yet Another Monster Fight

2huk · 2023-12-08 22:34:29 · 题解

Description

有 n 个怪物排成一排，每一个怪物有初始血量 a_i。当一个怪物的血量 \le 0 时，这个怪物就没了。

每次魔法需要选择一个起始位置 i，并给予 i 怪兽 x 的伤害。其中 i, x 都是可以任意选的。

然后每次需要选择一个没有被施魔法的且与一个已经施魔法的怪兽相邻的怪兽施魔法。若这个怪兽是第 j 次施的魔法，则它受的伤害为 x - j + 1。

请你选择一个初始血量 x 和起始位置 i，使得对于任意满足上述条件的施魔法的顺序都能将所有怪兽打败。请你求出最小的 x。

Solution

我们枚举第一个受攻击的怪兽 i，然后计算最坏情况下需要的初始血量 x。每一个 x 中的最小值即为答案。

考虑对于一个怪兽 j 而言，在能打败它的最坏情况下初始血量是多少：

综上，如果第一个攻击的怪兽是 i，最坏情况下最少的初始血量为：

定义 x_i = \max_{j = 1}^{i} (a_j + n - j)，y_i = \max_{j = i}^n(a_j + j - 1)，那么答案为：

很显然 x_i, y_i 可以 \mathcal O(n) 预处理，所以答案可以在 \mathcal O(n) 的时间复杂度内计算。

Code

int n, a[N]; 
int x[N], y[N], res = INF;

signed main()
{
    n = read();

    fup (i, 1, n) a[i] = read();
    fup (i, 1, n) x[i] = Max(x[i - 1], a[i] + n - i);
    fdw (i, n, 1) y[i] = Max(y[i + 1], a[i] + i - 1);

    fup (i, 1, n)
    {
        // 第一个目标为 i
        res = Min(res, Max(a[i], Max(x[i - 1], y[i + 1]))); 
    }

    wel(res);

    return 0;
}