翻來覆去 題解|APCS 2025 年 11 月高級 第 3 題
前置知識
滿分做法要用樹狀陣列,下面的講解直接把它當成已知,沒讀過的先讀:
- 樹狀陣列(Fenwick Tree/BIT):WiwiHo 的競程筆記〈樹狀數組〉的「單點修改」「前綴查詢」,OI Wiki〈树状数组〉(簡體中文)也有同樣的內容——支援「某個位置加減一個數」與「前綴和」兩種操作,各 \(O(\log n)\)。本題用它維護「每個位置的數字還在不在」,就能很快算出兩個位置之間還剩幾個數字。用線段樹也可以。
簡潔題意
兩個堆疊 \(S_1\)(空)與 \(S_2\)(由上到下是排列 \(p_1, p_2, \ldots, p_n\))。每次彈出某個堆疊的頂端:若它正好是下一個要輸出的數字就輸出,否則必須推入另一個堆疊。要依序輸出 \(1, 2, \ldots, n\),求最少的彈出次數(\(1 \le n \le 10^5\))。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(30\) 分):\(n \le 100\)。
- 子題組 2(\(70\) 分):無額外限制。
先拿下 30 分:照題意模擬
\(n \le 100\) 時直接用兩個 vector 當堆疊模擬:要輸出 \(x\) 時,找到它在哪個堆疊,把它上面的元素一個一個彈到另一個堆疊,再彈出 \(x\)。這樣做對嗎?\(x\) 上面的元素都比 \(x\) 大、現在不能輸出,它們每一個都至少要被彈一次才拿得到 \(x\),所以這些彈出省不掉;而先去彈另一個堆疊的頂端只是把一個更大的數疊到 \(x\) 上面,純粹多做工。因此每一步都是被迫的,沒有別的選擇。
彈出次數最多約 \(n^2 / 2 = 5000\),瞬間完成。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> stack1, stack2; // vector 的尾端當作堆疊頂端
vector<int> p(n);
for (int i = 0; i < n; i++) cin >> p[i];
// S2 由上到下是 p_1 ... p_n,所以 p_n 要先放進去(在最底下)
for (int i = n - 1; i >= 0; i--) stack2.push_back(p[i]);
long long answer = 0;
for (int x = 1; x <= n; x++) {
// x 在哪個堆疊?把它上面的元素一個一個彈到另一個堆疊,再彈出 x
bool in_stack2 = false;
for (int v : stack2) if (v == x) in_stack2 = true;
vector<int> &from = in_stack2 ? stack2 : stack1;
vector<int> &to = in_stack2 ? stack1 : stack2;
while (from.back() != x) {
to.push_back(from.back());
from.pop_back();
answer++;
}
from.pop_back(); // 彈出並輸出 x
answer++;
}
cout << answer << '\n';
return 0;
}
換個角度看:一個游標在一排數字上走
把 \(S_1\) 由底到頂、接著 \(S_2\) 由頂到底排成一排,一開始就是 \(p_1, p_2, \ldots, p_n\),兩個堆疊的頂端之間放一個游標(一開始在最左邊)。觀察一次「彈出並推入另一個堆疊」:
- 從 \(S_2\) 頂端彈出、推入 \(S_1\):那個數字在這一排裡位置不變,只是從游標右邊變成游標左邊——等於游標往右走一格。
- 從 \(S_1\) 彈到 \(S_2\) 同理,游標往左走一格。
- 彈出並輸出 \(x\):\(x\) 從這一排消失,游標停在 \(x\) 原本的位置。
所以整個過程就是:游標走到 \(1\) 旁邊、刪掉 \(1\);走到 \(2\) 旁邊、刪掉 \(2\)……彈出次數 \(=\) 游標走的步數 \(+ n\),而游標從上一個數字的位置走到下一個數字,步數就是兩個位置之間還沒被刪掉的數字個數。
以範例 2 的 3 2 4 1 為例:游標從最左邊走到 \(1\),中間有 \(3, 2, 4\) 三個,共 \(3 + 1 = 4\) 次;接著走到 \(2\),中間只剩 \(4\),共 \(2\) 次;走到 \(3\) 中間沒有東西,\(1\) 次;走到 \(4\) 中間的 \(2\) 已經刪掉了,\(1\) 次。總共 \(8\) 次。
從 30 分到 100 分:用樹狀陣列算「中間還剩幾個」
令 pos[x] 為 \(x\) 一開始的位置,樹狀陣列裡位置 \(i\) 的值是 \(1\)(還在)或 \(0\)(已刪)。依序處理 \(x = 1, 2, \ldots, n\):游標在位置 cursor(上一個數字的位置,已經是空的),\(x\) 在 pos[x],兩者之間還剩的數字個數就是一段區間和;答案加上它再加 \(1\),然後把 pos[x] 改成 \(0\)、游標移到 pos[x]。
每個數字一次區間和、一次單點更新,總共 \(O(n \log n)\)。答案最大約 \(n^2 / 2 = 5 \times 10^9\),要用 long long。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
int n;
int pos[MAX_N + 1]; // pos[x]:數字 x 一開始在序列中的位置(1 ~ n)
int bit[MAX_N + 1]; // 樹狀陣列:位置 i 的數字還在序列裡就是 1
void add(int i, int v) {
for (; i <= n; i += i & -i) bit[i] += v;
}
int prefix(int i) { // 位置 1 ~ i 還剩幾個數字
int total = 0;
for (; i > 0; i -= i & -i) total += bit[i];
return total;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int p;
cin >> p;
pos[p] = i;
add(i, 1);
}
long long answer = 0;
int cursor = 0; // 游標目前在位置 cursor 的右邊;一開始在整個序列的最左邊
for (int x = 1; x <= n; x++) {
int lo = min(cursor, pos[x]), hi = max(cursor, pos[x]);
int between = prefix(hi - 1) - prefix(lo); // 游標與 x 之間還剩幾個數字
answer += between + 1; // 走過去各彈一次,再彈出 x 本身
add(pos[x], -1); // x 輸出了,從序列移除
cursor = pos[x]; // 游標停在 x 原本的位置
}
cout << answer << '\n';
return 0;
}
測過再交:範例的數字都很少
兩個範例只有 \(3\)、\(4\) 個數字,答案是 \(4\) 和 \(8\)。沒蓋到的:只有一個數字、整排倒過來,還有答案大到超過 int 的情況。第 2 列是很小、卻能抓出一種兩個範例都會過的錯法(見常犯錯誤)。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 / 1 |
1 |
最小的 \(n\):直接彈出並輸出 |
3 / 2 3 1 |
6 |
先把 \(2\)、\(3\) 彈到 \(S_1\)(\(S_1\) 頂端變成 \(3\)),要輸出 \(2\) 時得先把 \(3\) 彈回去 |
5 / 5 4 3 2 1 |
9 |
整排倒過來:游標先走到最右邊,再一格一格往回走 |
| 用程式造:\(n = 10^5\),排列是 \(2, 4, 6, \ldots, 100000, 99999, \ldots, 5, 3, 1\) | 5000050000 |
答案超過 int;照子題組 1 模擬要彈 \(5 \times 10^9\) 次 |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- \(S_2\) 放反了(\(p_1\) 放在最底下):題目說 \(p_1\) 在頂端。範例 1 剛好會過,範例 2 會印
5。 - 答案用
int:範例全過;自測表第 4 列會印705082704,本站 \(20\) 筆掛 \(1\) 筆。 - \(n = 10^5\) 還照子題組 1 一個一個彈:自測表第 4 列要彈 \(5 \times 10^9\) 次,\(1\) 秒跑不完;本站 \(20\) 筆至少 \(6\) 筆超時。
- 模擬時把一整段「搬」到另一疊卻保留原本的順序:一個一個彈過去,順序會反過來。範例全過;自測表第 2 列會算成
5。