r628. 3. 翻來覆去 - 高中生程式解題系統

內容

給定一個長度為 $n$ 的排列（Permutation） $P = (p_1, p_2, \dots, p_n)$，包含從 $1$ 到 $n$ 的所有整數。一開始，所有元素都按照它們在 $P$ 中的順序，從 $p_n$ 到 $p_1$ 依次被壓入 Stack $S_2$ 中（即 $p_n$ 在底，$p_1$ 在頂）。

目標是要透過這兩個 stack 的 push 和 pop 操作來將這個排列做由小到大排序，並且輸出最少需要多少 pop 操作。

以範例測資2 為例，目前的兩個 stack 為 [], [4, 2, 3, 1]

操作	堆疊狀態
	[ ], [3, 2, 4, 1]
s2.pop() s1.push(3)	[3], [2, 4, 1]
s2.pop(), s1.push(2)	[2, 3], [4, 1]
s2.pop(), s1.push(4)	[4, 2, 3], [1]
s2.pop() 獲得1	[4, 2, 3], []
s1.pop(), s2.push(4)	[2, 3], [4]
s1.pop() 獲得2	[3], [4]
s1.pop() 獲得3	[], [4]
s2.pop() 獲得4	[], []

總共花費 8 次 pop 操作。

輸入說明

第一行輸入一個正整數 $n$ ($1 \le n \le 10^5$)，接下來一行為 $1$ 到 $n$ 的一個排列。

$30$分: $n \le 100$
$70$分: 無限制

輸出說明

輸出需要多少 pop 操作才能將這個排列由小到大排序好。

範例輸入 #1

3
3 1 2

範例輸出 #1

範例輸入 #2

4
3 2 4 1

範例輸出 #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

標籤:

APCS

出處:

APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
54081	ericshen1955 ... (暴力又被TLE)	r628	Python x Cpp 題解 - 樹狀數組 Binary Indexed Tree + Bitset 分塊壓常 - 分治又肥又慢，你看看 BIT 他多香(吸)	245	2025-11-18 20:50
54102	cubeman94033 ... (請輸入暱稱)	r628	解題報告	78	2025-11-22 02:46
54070	guovinn@gmai ... (郭10)	r628	c++題解（內含程式碼與思路）	262	2025-11-17 11:20