翻來覆去 (APCS 2025-11 高級)
1.0s 256M有一個排列 \(P = (p_1, p_2, \ldots, p_n)\),其中包含 \(1\) 到 \(n\) 的每個整數各一次。
一開始有兩個堆疊 \(S_1, S_2\)。\(S_1\) 是空的,\(S_2\) 從上到下依序是 \(p_1, p_2, \ldots, p_n\)。也就是說,\(p_1\) 在 \(S_2\) 的頂端,\(p_n\) 在 \(S_2\) 的底部。
每次操作你可以選擇其中一個非空堆疊,彈出它頂端的元素。若這個元素剛好是目前要輸出的下一個數字,就把它輸出;否則必須把它推入另一個堆疊。
你的目標是依序輸出 \(1, 2, \ldots, n\)。請計算最少需要幾次彈出操作。
輸入格式
第一行包含一個整數 \(n\)。
第二行包含 \(n\) 個整數 \(p_1, p_2, \ldots, p_n\),代表排列 \(P\)。
限制
- \(1 \le n \le 10^5\)
- \(P\) 是 \(1\) 到 \(n\) 的排列
輸出格式
輸出一個整數,代表最少需要的彈出操作次數。
評分說明
每一筆測試資料的執行時間限制均為 \(1\) 秒,依正確通過的測試資料筆數給分。
| 子題組 | 分數 | 額外限制 |
|---|---|---|
| 1 | 30 | \(n \le 100\) |
| 2 | 70 | 無額外限制 |
範例輸入 1
3
3 1 2
範例輸出 1
4
範例解釋 1
一開始 \(S_2\) 的頂端是 \(3\)。先把 \(3\) 彈出並推入 \(S_1\),接著從 \(S_2\) 依序彈出並輸出 \(1, 2\),最後從 \(S_1\) 彈出並輸出 \(3\),共需要 \(4\) 次彈出。
範例輸入 2
4
3 2 4 1
範例輸出 2
8
範例解釋 2
一種最少操作方式如下:
彈出 3,推入另一個堆疊
彈出 2,推入另一個堆疊
彈出 4,推入另一個堆疊
彈出並輸出 1
彈出 4,推入另一個堆疊
彈出並輸出 2
彈出並輸出 3
彈出並輸出 4
因此答案是 \(8\)。
題目來源
APCS 2025 年 11 月高級實作題第 3 題。
題敘參考 ZeroJudge r628「翻來覆去」 整理,細節可能與正式試題有出入。