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

🔗 ABC388D Coming of Age Celebration

Problem Statement

題目簡述

有 NN 個外星人，第 ii 個外星人目前有 AiA_i 顆石頭，並將在 ii 年後成年。
當一個外星人成年時，所有已經成年且至少有一顆石頭的外星人，都會給這個剛成年的外星人恰好 11 顆石頭。
請問 NN 年後，每個外星人分別擁有多少顆石頭？

Constraints

約束條件

  • 1≤N≤5×1051 \leq N \leq 5 \times 10^5
  • 0≤Ai≤5×1050 \leq A_i \leq 5 \times 10^5
  • 所有輸入皆為整數。

思路：反向模擬 + 差分陣列

為什麼不能直接模擬？

題目描述了一個「成年人互相送石頭」的過程：每當有人成年，所有已經成年且還有石頭的人，都會送他一顆。直接模擬的話，每處理一個人就要回頭檢查前面所有人，時間是 O(N2)\mathcal{O}(N^2)，在 N=5×105N = 5 \times 10^5 下不可行。

關鍵觀察

瓶頸在於「回頭找誰有石頭」。如果反過來想：每個人成年後，送出的石頭只會影響他後面的人，那我們就可以把影響往後推，而不是每次都回頭檢查。

反向思考：先決定他能影響誰

假設我們按成年順序（也就是編號順序）逐一處理每個人。當輪到某個人成年時，有兩件事需要確定：

  1. 他目前有多少石頭？ — 初始石頭 + 前面的人送他的石頭。
  2. 他會送出多少石頭？ — 他會從緊接在他後面的那個人開始，一個一個送，直到石頭送完或後面沒人了。

因此實際送出的數量就是：

min⁡(當前石頭數, 後面剩下的人數)\min(\text{當前石頭數},\ \text{後面剩下的人數})

送出的這些石頭會形成一段連續影響：從下一個人開始，連續若干個人各收到一顆。

用差分陣列記錄未來收入

「把一個區間內每個人的預期收入加 11」是典型的區間加值操作。如果每次都用迴圈逐個加，又回到了 O(N2)\mathcal{O}(N^2)，我們可以用差分陣列優化這個過程。

差分陣列維護的是「每個人在成年時，會從前面的人那裡收到幾顆石頭」。掃到某個人時，先用差分前綴和得到他實際收到的石頭數，再計算他能送出多少顆，並把這個影響更新到後方的連續區間。

最後，某個人的答案就是：

初始石頭數+收到的石頭數−送出的石頭數\text{初始石頭數} + \text{收到的石頭數} - \text{送出的石頭數}

複雜度分析

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N = int(input())
A = list(map(int, input().split()))

d = [0] * (N + 1)
ans = [0] * N
cur = 0  # 收到的石頭數量，對差分陣列做前綴和得到
for i, x in enumerate(A):
    cur += d[i]
    give = min(x + cur, N - 1 - i)  # 給出的石頭數量
    if give > 0:
        # 區間 [i + 1, i + give] 的石頭數量增加 1
        d[min(i + 1, N)] += 1
        d[min(i + give + 1, N)] -= 1
    ans[i] = x + cur - give
print(*ans)