砍樹 題解｜APCS 2020 年 1 月中高級 第 3 題
前置知識
這題的核心推導（一棵樹能不能倒只看還站著的左右鄰居）下面會從頭講；要先會的是兩個工具，同一個主題兩邊都有的，對照著讀會更快上手：
- 鏈結串列：NTUCPC Guide〈Linked List〉——用兩個陣列
prv[]、nxt[]記每個元素的前後是誰，拿掉一個元素只要改兩個值；吳邦一《AP325》第 3 章的「串列鏈結」一節就是拿本題（例題 P-3-6）當例子，\(O(n^2)\) 版、串列加佇列版、堆疊版三種寫法都有（教材 PDF 第 99～105 頁；Python 版第 3 章）。 - 佇列：NTUCPC Guide〈Stack、Queue 與 Deque〉——「要重新檢查的東西排隊，輪到了再看」。
簡潔題意
\(N\) 棵樹長在 \([0, L]\) 上，位置 \(c_i\) 由小到大給、高度 \(h_i\)。砍一棵樹要讓它向左倒（蓋住 \([c_i - h_i, c_i]\)）或向右倒（蓋住 \([c_i, c_i + h_i]\)），倒下的範圍不能超出 \([0, L]\)、裡面不能有還站著的樹，別的樹剛好在端點不算壓到。能砍就砍、砍到沒有樹能砍為止（最後砍掉的集合跟順序無關），輸出砍掉幾棵、以及砍掉的樹裡最高的高度（沒砍到任何樹就印 0）（\(1 \le N \le 10^5\)，\(1 \le L \le 10^9\)，\(1 \le h_i \le 10^9\)）。
依正確通過的測試資料筆數給分，其中：
- 子題組 1（\(30\) 分）：\(N \le 1000\)。
- 子題組 2（\(70\) 分）：無額外限制。
一棵樹能不能倒：只看還站著的左右鄰居
第 \(i\) 棵樹向左倒蓋住 \([c_i - h_i, c_i]\)，這段裡會不會有別的樹，只需要看目前還站著的左鄰居：它的位置 \(c_l\) 不在 \((c_i - h_i, c_i)\) 裡就行（更左邊的樹更不可能在裡面）。「剛好在端點不算壓到」，所以 \(c_l = c_i - h_i\) 是允許的——條件寫成 \(c_l \le c_i - h_i\)，等號要留著。向右倒同理：\(c_i + h_i \le L\)，而且右鄰居 \(c_r \ge c_i + h_i\)。兩個方向有一個行就能砍（圖 1）。
砍掉一棵樹，只有它的左右鄰居會受影響：鄰居的「最近的還站著的樹」換人了，原本被擋住的方向可能空出來——範例裡 \(1\) 號一開始向右被 \(2\) 號擋住，\(2\) 號砍掉後就倒得下。其他樹的鄰居沒變，不用重看。
座標和高度都到 \(10^9\)，\(c_i + h_i\) 最大 \(2 \times 10^9\)，還在 int 的 \(2147483647\) 以內，不過很接近；不想算就用 long long，兩種都對（估算方法見語法書 2.9）。
先拿下 30 分：有砍到就再掃一輪
最直接的寫法：從左到右掃一遍，能砍的就砍；只要這一輪有砍到樹，就再掃一輪，直到一整輪都沒砍到為止。找「最近的還站著的鄰居」就往左、往右跳過已經砍掉的樹。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
int n;
long long L, c[MAX_N + 2], h[MAX_N + 2];
bool cut[MAX_N + 2]; // 這棵樹砍掉了沒
int main() {
cin >> n >> L;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> h[i];
int count = 0;
long long tallest = 0;
bool changed = true;
while (changed) { // 這一輪有砍到樹，就再掃一輪
changed = false;
for (int i = 1; i <= n; i++) {
if (cut[i]) continue;
int l = i - 1, r = i + 1; // 往左右找最近「還站著」的樹
while (l >= 1 && cut[l]) l--;
while (r <= n && cut[r]) r++;
bool left = c[i] - h[i] >= 0 && (l == 0 || c[l] <= c[i] - h[i]);
bool right = c[i] + h[i] <= L && (r == n + 1 || c[r] >= c[i] + h[i]);
if (left || right) {
cut[i] = true;
count++;
tallest = max(tallest, h[i]);
changed = true;
}
}
}
cout << count << endl << tallest << endl;
return 0;
}
一輪最少砍一棵，所以最多 \(N\) 輪、每輪掃 \(N\) 棵，\(O(N^2)\)：\(N = 1000\) 時 \(10^6\)，一瞬間，子題組 1 的 \(30\) 分穩穩到手。\(N = 10^5\) 時最壞的情況是「每一輪只有最右邊那棵能倒」——每棵樹都被右鄰居擋住、只能等右邊的倒了自己才能倒，這樣要掃 \(N\) 輪，本站實測 \(17\) 秒。
從 30 分到 100 分：只重看鄰居
重掃一整輪很浪費：砍掉一棵樹只會讓它的左右鄰居變得可能能砍，其他樹看了也是白看。所以改成排隊：一開始每棵樹都排隊檢查一次；輪到的樹若能砍就砍掉，並且把它的左右鄰居重新排隊。鄰居是誰，用鏈結串列 prv[]、nxt[] 維護——砍掉 \(i\) 就把 prv[i] 和 nxt[i] 直接接起來，之後查鄰居都是 \(O(1)\)，不用再跳過砍掉的樹。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
int n;
long long L, c[MAX_N + 2], h[MAX_N + 2];
bool cut[MAX_N + 2];
int prv[MAX_N + 2], nxt[MAX_N + 2]; // 目前還站著的左右鄰居（0 和 n + 1 代表沒有鄰居）
bool canCut(int i) {
bool left = c[i] - h[i] >= 0 && (prv[i] == 0 || c[prv[i]] <= c[i] - h[i]);
bool right = c[i] + h[i] <= L && (nxt[i] == n + 1 || c[nxt[i]] >= c[i] + h[i]);
return left || right;
}
int main() {
cin >> n >> L;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) {
prv[i] = i - 1;
nxt[i] = i + 1;
}
queue<int> q; // 等著被檢查的樹
for (int i = 1; i <= n; i++) q.push(i); // 每棵樹先排隊檢查一次
int count = 0;
long long tallest = 0;
while (!q.empty()) {
int i = q.front();
q.pop();
if (cut[i] || !canCut(i)) continue;
cut[i] = true;
count++;
tallest = max(tallest, h[i]);
int l = prv[i], r = nxt[i];
nxt[l] = r; // 把 i 從串列中拿掉：左右鄰居直接相連
prv[r] = l;
if (l >= 1) q.push(l); // 鄰居的情況變了，重新排隊檢查
if (r <= n) q.push(r);
}
cout << count << endl << tallest << endl;
return 0;
}
每棵樹最多被砍一次，每砍一次只多排兩棵樹進佇列，所以總共檢查不超過 \(3N\) 次，\(O(N)\)；\(N = 10^5\) 本站實測不到 \(0.1\) 秒。同一棵樹可能在佇列裡出現好幾次，砍掉後再輪到它就靠 cut[i] 直接跳過。
測過再交：範例一棵都沒卡在邊界上
範例六棵樹有連鎖（\(2\) 號砍掉 \(1\) 號才能倒）、有砍不掉的（\(3\)、\(5\) 號），但沒蓋到：一棵都砍不掉要印兩個 0、剛好倒在 \(0\) 或 \(L\) 上、剛好碰到鄰居的端點、以及「要從最右邊一路往左連鎖」的大測資（驗速度）。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 10／5／6 |
0／0 |
兩個方向都超出範圍：一棵都砍不掉，第二行要印 0 |
1 10／5／5 |
1／5 |
剛好倒在 \(L\) 上（\(5 + 5 = 10\)）：允許 |
2 10／1 3／2 9 |
1／2 |
\(1\) 號向右倒剛好碰到 \(3\) 號的位置 \(3\)：端點不算壓到，能砍；\(2\) 號兩邊都不行 |
3 20／5 10 15／6 3 6 |
3／6 |
連鎖：只有中間的 \(2\) 號一開始能倒，砍掉它之後左右兩棵才倒得下 |
4 100／10 20 30 40／15 15 15 15 |
4／15 |
從右往左連鎖：每棵都被右鄰居擋住，最右邊那棵倒了才一棵接一棵倒 |
| 用程式造：\(N = 100000\)，\(c_i = 10i\)、\(h_i = 15\)、\(L = 10^6 + 20\) | 100000／15 |
上一列放大到 \(10^5\) 棵：重掃一整輪的寫法要跑 \(N\) 輪，超時 |
六筆都親眼看過正確，這題就穩了。
另一種做法：從左到右一路掃、用堆疊
這是《AP325》裡「更簡單的作法」：從左到右處理，用一個堆疊 standing 放「掃過了、暫時砍不掉」的樹。輪到第 \(i\) 棵時，它的左鄰居就是堆疊頂端那棵，右鄰居一定是還沒處理的第 \(i + 1\) 棵。能砍就砍，砍掉之後堆疊頂端那棵的右鄰居變成了 \(i + 1\)，它可能因此能向右倒——倒了再看下一個頂端，用 while 一路往回檢查。砍不掉就把 \(i\) 推進堆疊。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
int n;
long long L, c[MAX_N + 2], h[MAX_N + 2];
bool fallLeft(int i, int l) { // l = 左鄰居（0 代表沒有）
return c[i] - h[i] >= 0 && (l == 0 || c[l] <= c[i] - h[i]);
}
bool fallRight(int i, int r) { // r = 右鄰居（n + 1 代表沒有）
return c[i] + h[i] <= L && (r == n + 1 || c[r] >= c[i] + h[i]);
}
int main() {
cin >> n >> L;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> h[i];
vector<int> standing; // 掃過、暫時砍不掉的樹（由左到右）
int count = 0;
long long tallest = 0;
for (int i = 1; i <= n; i++) {
int l = standing.empty() ? 0 : standing.back(); // 左鄰居就是最後一棵還站著的
if (fallLeft(i, l) || fallRight(i, i + 1)) { // 右鄰居此時一定是 i + 1
count++;
tallest = max(tallest, h[i]);
// i 倒了，standing 最後那棵的右鄰居變成 i + 1：可能換它倒，一路往回檢查
while (!standing.empty() && fallRight(standing.back(), i + 1)) {
count++;
tallest = max(tallest, h[standing.back()]);
standing.pop_back();
}
} else {
standing.push_back(i);
}
}
cout << count << endl << tallest << endl;
return 0;
}
為什麼只看向右倒就夠：堆疊裡一棵樹的左鄰居（它下面那棵）在它還沒被砍掉之前永遠不會變，所以向左倒的機會在它被推進堆疊時就已經判過了。每棵樹進出堆疊各一次，\(O(N)\)。兩種做法都是滿分；佇列版比較不容易漏掉情況，堆疊版比較短。
常犯錯誤
- 端點算成壓到（條件寫成 \(c_l < c_i - h_i\)）：範例印
3／30，正確是4／30；自測表第 3 列印0／0。 - 沒檢查倒下的範圍會不會超出 \([0, L]\)：範例印
6／55；自測表第 1 列印1／6。 - 第二行印全部樹裡最高的，不是砍掉的樹裡最高的：範例印
4／55。 - 砍掉一棵樹後沒有重新檢查它的鄰居（佇列版只排隊一次、或者只從左到右掃一遍）：範例印
3／25——\(1\) 號沒機會在 \(2\) 號倒了之後再看一次；自測表第 5 列印1／15。 - 砍掉後沒更新串列，鄰居還是砍之前那棵：範例印
3／25；自測表第 4 列印1／3。 - 堆疊版把
while寫成if（砍掉一棵後只回頭看一棵）：範例過，計分測資掛 \(2\) 筆；自測表第 5 列印2／15。 - 重掃一整輪的 \(30\) 分版硬交：\(N = 10^5\) 從右往左連鎖的測資本站實測 \(17\) 秒，超時。