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

🔗 ABC438C 1D puyopuyo

Problem Statement

題目簡述

給定長度為 NN 的整數序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。
可以重複進行以下操作任意次，也可以不操作：選擇序列中連續 44 個相同的元素，並將它們從序列中刪除。
請求出經過若干次操作後，序列長度的最小可能值。

Constraints

約束條件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤Ai≤N1 \leq A_i \leq N
  • 輸入皆為整數

思路：堆疊模擬

為什麼可以用堆疊模擬？

題目允許在「任意位置」刪除連續 44 個相同的元素。對於這類相鄰消除問題，無論以什麼順序進行消除，最終無法再消除的序列都是唯一確定的。
因此，我們不需要考慮複雜的消除順序，直接採取由左至右貪心消除的策略即可，而「堆疊」正是處理這類由左至右相鄰消除的最佳資料結構。

模擬消除過程

我們維護一個堆疊，依序將序列的元素放入：

  1. 每次準備放入新元素時，檢查堆疊頂端是否已經有連續 33 個與新元素相同的元素。
  2. 如果有，代表加上新元素剛好湊滿 44 個，此時直接將堆疊頂端的 33 個元素彈出（等同於這 44 個元素一起被消除），且新元素不入疊。
  3. 如果沒有，則將新元素推入堆疊。

當所有元素都處理完畢後，堆疊內剩下的元素數量即為無法再消除的最小長度。

複雜度分析

  • 時間複雜度：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
16
17
def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    st = []
    for x in A:
        if len(st) >= 3 and st[-1] == x and st[-2] == x and st[-3] == x:
            for _ in range(3):
                st.pop()
        else:
            st.append(x)
    print(len(st))


if __name__ == "__main__":
    solve()