翻來覆去 (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「翻來覆去」 整理,細節可能與正式試題有出入。

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器(per 帳號 / 題目 / 語言)。
  • 提交 — 把程式碼交給 judge 評測,回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB (約 100 萬字元)
  • 自訂測試每人約 3 秒 1 次 (範例測試 1 秒 1 次)
  • 自訂測試有 15 秒 牆鐘上限;範例測試和正式評測一樣,照題目的時間限制
  • 互動題不提供自訂測試(無法模擬與 judge 互動)。
  • 提交評測本身沒有 rate limit,但同題短時間內多次提交會被視為刷分。