題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC435C Domino

Problem Statement

題目簡述

有 nn 個骨牌排成一列，第 ii 個骨牌位於座標 ii，高度為 AiA_i。
當第 ii 個骨牌向右倒下時，範圍 [i,i+Ai−1][i, i+A_i-1] 內的所有骨牌都會倒下。
若第 1 個骨牌向右倒下，求最終總共有多少個骨牌倒下。

Constraints

約束條件

  • 1≤n≤5×1051 \le n \le 5 \times 10^5
  • 1≤Ai≤n1 \le A_i \le n
  • 輸入皆為整數

思路：模擬 (Simulation)

依序遍歷每個被觸及的骨牌，維護當前能夠到達的最遠位置 rr。
當到達新的位置 ii 時，更新 r=max(r,i+Ai−1)r = max(r, i + A_i - 1)。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)
  • 空間複雜度：O(n)\mathcal{O}(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    i = r = 0
    while i <= min(r, n - 1):
        r = max(r, i + A[i] - 1)
        i += 1
    print(i)

if __name__ == "__main__":
    solve()