花与风 题解

---

一、题目回顾

有 $n$ 朵花排成一排，第 $i$ 朵初始高度为 $h_i$。每一秒，风从左边吹来，对每个 $i$ 从 $1$ 到 $n$：

• 若 $i = n$ 或 $h_i > h_{i+1}$，则 $h_i \gets \max(0, h_i - 1)$。

求所有花高度首次全部变为 $0$ 所需的秒数。

---

二、核心结论

答案 = $\displaystyle\max_{i=1}^{n} \big( h_i + i - 1 \big)$

---

三、推导过程

3.1 从右向左的递推

设 $g(i)$ 表示第 $i$ 朵花到第 $n$ 朵花全部变为 $0$ 所需的秒数。

• 最右端：$g(n) = h_n$，因为第 $n$ 朵花每秒钟都会减少 $1$。

• 对于 $i < n$：

  • 若 $h_i \le g(i+1)$：第 $i$ 朵花的高度较小，在右边全部清零之前它可能已经"被顺带"减了不少。可以证明它恰好需要 $g(i+1) + 1$ 秒。
  • 若 $h_i > g(i+1)$：第 $i$ 朵花自身太高，它成为新的瓶颈，需要 $h_i$ 秒。

  综合得到递推式：

  $$g(i) = \max\big(g(i+1) + 1,\; h_i\big)$$

3.2 展开递推

从 $i = n-1$ 向下展开到 $1$：

$$\begin{aligned} g(n) &= h_n \\ g(n-1) &= \max(h_n + 1,\; h_{n-1}) \\ g(n-2) &= \max(h_n + 2,\; h_{n-1} + 1,\; h_{n-2}) \\ &\;\;\vdots \\ g(1) &= \max\big(h_n + (n-1),\; h_{n-1} + (n-2),\; \dots,\; h_2 + 1,\; h_1\big) \end{aligned} $$

即：

$$\boxed{g(1) = \max_{i=1}^{n} \big( h_i + i - 1 \big)} $$

其中 $h_i$ 的系数恰好是 $i-1$（该花左边花的朵数）。

3.3 直观理解

• $h_i$：第 $i$ 朵花自身需要被减少的次数。
• $i-1$：第 $i$ 朵花左边的花每朵都会"耽误"它至少 $1$ 秒——因为左边的花优先被风吹，等它们降到足够低时，风才会"照顾"到更右边的花。左边的花越多，延迟越久。

最终答案由最大的瓶颈位置决定。

---

四、复杂度

• 每组测试数据只需扫描一次数组，$O(n)$。
• 所有测试数据 $\sum n \le 10^5$，总复杂度 $O(\sum n)$。

---

五、AC 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 10;

inline int read() {
    int r = 0, w = 1;
    char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { r = (r << 3) + (r << 1) + (c ^ 48); c = getchar(); }
    return r * w;
}

int T, n, a[N];

signed main() {
    T = read();
    while (T--) {
        n = read();
        for (int i = 1; i <= n; ++i) a[i] = read();

        // 从右向左递推，a[n] 存储答案
        for (int i = n - 1; i >= 1; --i)
            a[n] = max(a[n] + 1, a[i]);

        cout << a[n] << "\n";
    }
    return 0;
}